【HAOI2007】理想的正方形

 1 #include <cstdlib>
 2 #include <iostream>
 3 #include <cmath>
 4 #include <cstdio>
 5 #include <cstring>
 6 const int MAX=1010;
 7 const int INF=0x7fffffff;
 8 using namespace std;
 9 //注意Max与Min(i,j)代表第i行从 
10 int data[MAX][MAX],Max[MAX][MAX],Min[MAX][MAX];
11 int a,b,n,ans=INF;
12 
13 void init();//输入数据
14 void solve();
15 void prepare(int hang);
16 void work(int lie);
17 
18 int main()
19 {
20     //文件操作
21     freopen("square.in","r",stdin);
22     freopen("square.out","w",stdout);
23     init();//输入数据 
24     solve();//求解 
25     return 0;
26 }
27 void init()
28 {
29     scanf("%d%d%d",&a,&b,&n);
30     for (int i=1;i<=a;i++)
31     for (int j=1;j<=b;j++) 
32     scanf("%d",&data[i][j]);
33 }
34 void solve()
35 {
36      //计算出每行各个元素的最大值与最小值 
37      for (int i=1;i<=a;i++) prepare(i);//横推行 
38     // printf("\n");
39      for (int i=n;i<=b;i++) work(i);//纵推列 
40      printf("%d\n",ans);
41 }
42 void prepare(int hang)
43 {
44      int Q_MAX[MAX],front_MAX=1,rear_MAX=1;
45      int Q_MIN[MAX],front_MIN=1,rear_MIN=1;
46      for (int i=1;i<=n;i++)//预处理 
47      {
48          while (front_MAX<rear_MAX && data[hang][Q_MAX[rear_MAX]]<data[hang][i]) rear_MAX--;
49          Q_MAX[++rear_MAX]=i;
50          while (front_MIN<rear_MIN && data[hang][Q_MIN[rear_MIN]]>data[hang][i]) rear_MIN--;
51          Q_MIN[++rear_MIN]=i;
52      }
53      //开始计算,千万要注意边界问题 
54      for (int i=n;i<=b;i++)
55      {
56          //先计算MAX与MIN值 
57          while (front_MAX<rear_MAX && Q_MAX[front_MAX+1]<(i-n+1)) front_MAX++; 
58          Max[hang][i]=data[hang][Q_MAX[front_MAX+1]];
59          while (front_MIN<rear_MIN && Q_MIN[front_MIN+1]<(i-n+1)) front_MIN++; 
60          Min[hang][i]=data[hang][Q_MIN[front_MIN+1]];
61          //再考虑加入队列 
62          while (front_MAX<rear_MAX && data[hang][Q_MAX[rear_MAX]]<data[hang][i+1]) rear_MAX--;
63          Q_MAX[++rear_MAX]=i+1;         
64          while (front_MIN<rear_MIN && data[hang][Q_MIN[rear_MIN]]>data[hang][i+1]) rear_MIN--;
65          Q_MIN[++rear_MIN]=i+1;
66      }
67      //打印
68      //for (int i=n;i<=b;i++) printf("(%d %d) ",Max[hang][i],Min[hang][i]);
69     // printf("\n"); 
70 } 
71 void work(int lie)
72 {
73      //printf("%d:",lie);
74      int Q_MAX[MAX],front_MAX=1,rear_MAX=1;
75      int Q_MIN[MAX],front_MIN=1,rear_MIN=1;
76      for (int i=1;i<=n;i++)//预处理,注意这里换成行了 
77      {
78          while (front_MAX<rear_MAX && Max[Q_MAX[rear_MAX-1]][lie]<Max[i][lie]) rear_MAX--;
79          Q_MAX[rear_MAX++]=i;
80          while (front_MIN<rear_MIN && Min[Q_MIN[rear_MIN-1]][lie]>Min[i][lie]) rear_MIN--;
81          Q_MIN[rear_MIN++]=i;
82      }
83      //开始计算,千万要注意边界问题 
84      for (int i=n;i<=a;i++)
85      {
86          while (front_MAX<rear_MAX && Q_MAX[front_MAX]<(i-n+1)) front_MAX++; 
87          while (front_MIN<rear_MIN && Q_MIN[front_MIN]<(i-n+1)) front_MIN++; 
88          ans=min(ans,Max[Q_MAX[front_MAX]][lie]-Min[Q_MIN[front_MIN]][lie]);
89          
90          //printf("(%d %d) ",Q_MAX[front_MAX],Q_MIN[front_MIN]);
91          //再考虑加入队列 
92          while (front_MAX<rear_MAX && Max[Q_MAX[rear_MAX-1]][lie]<Max[i+1][lie]) rear_MAX--;
93          Q_MAX[rear_MAX++]=i+1;         
94          while (front_MIN<rear_MIN && Min[Q_MIN[rear_MIN-1]][lie]>Min[i+1][lie]) rear_MIN--;
95          Q_MIN[rear_MIN++]=i+1;
96      }
97      //printf("\n");
98 }