Description
有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值
的差最小。
Input
第一行为3个整数,分别表示a,b,n的值第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数。每
行相邻两数之间用一空格分隔。
100%的数据2<=a,b<=1000,n<=a,n<=b,n<=1000
Output
仅一个整数,为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。
Sample Input
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
Sample Output
1
Solution
这题可以用单调队列先维护一下行再维护下列。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=1010; int A,B,n,a[N][N],ans,q[N],num[N],Max[N][N],Min[N][N],MAX[N],MIN[N]; void First() { for (int i=1;i<=A;i++) { int l=1,r=0; for (int j=1;j<=B;j++) { while (l<=r&&q[r]<=a[i][j]) r--; q[++r]=a[i][j];num[r]=j; if (num[l]<=j-n) l++; if (j>=n) Max[i][j]=q[l]; } l=1,r=0; for (int j=1;j<=B;j++) { while (l<=r&&q[r]>=a[i][j]) r--; q[++r]=a[i][j];num[r]=j; if (num[l]<=j-n) l++; if (j>=n) Min[i][j]=q[l]; } } } void Get() { for (int i=n;i<=B;i++) { int l=1,r=0; for (int j=1;j<=A;j++) { while (l<=r&&q[r]<=Max[j][i]) r--; q[++r]=Max[j][i];num[r]=j; if (num[l]<=j-n) l++; if (j>=n) MAX[j]=q[l]; } l=1,r=0; for (int j=1;j<=A;j++) { while (l<=r&&q[r]>=Min[j][i]) r--; q[++r]=Min[j][i];num[r]=j; if (num[l]<=j-n) l++; if (j>=n) MIN[j]=q[l]; } for (int j=n;j<=A;j++) ans=min(ans,MAX[j]-MIN[j]); } } int main() { scanf("%d%d%d",&A,&B,&n); for (int i=1;i<=A;i++) for (int j=1;j<=B;j++) scanf("%d",&a[i][j]); First(); ans=1<<30; Get(); printf("%d\n",ans); return 0; } |