「BZOJ1047」[HAOI2007] 理想的正方形
Description
有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
Input
第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。
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
问题规模
（1）矩阵中的所有数都不超过1,000,000,000
（2）20%的数据2<=a,b<=100,n<=a,n<=b,n<=10
（3）100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100
问题规模
（1）矩阵中的所有数都不超过1,000,000,000
（2）20%的数据2<=a,b<=100,n<=a,n<=b,n<=10
（3）100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100
题解
由于网上的题解都太神了，我就自己乱搞了
首先预处理每个点向左n个格子的范围内的最值记为t1与t2
对于每一行维护俩次单调队列解决。。。
那么每个正方形的最值就是右上角到右下角这一列内的所有格子的t1/t2的最值
再按列枚举，得出每个点为右下角的正方形最值，即向上n个格子的t1/t2的最值，更新答案
类似行上维护俩次单调队列
说白了就是把行上的每n个数压成了一个数，再在列上做单调队列
其实代码看起来长但是都是复制粘贴
我克制了自己不用stlT T但是常数还是。。。
|
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 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<cmath> #include<algorithm> #include<map> #include<deque> #define inf 2000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int a,b,n; int v[1005][1005],mx[1005][1005],mn[1005][1005],t1[1005],t2[1005]; int val[1005],pos[1005]; void pre() { int l,r; for(int i=1;i<=a;i++) { l=1,r=1; for(int j=1;j<=b;j++) { while(l<r&&val[r-1]<=v[i][j])r--; val[r]=v[i][j];pos[r]=j;r++; if(pos[l]==j-n)l++; if(j>=n)mx[i][j]=val[l]; } l=1,r=1; for(int j=1;j<=b;j++) { while(l<r&&val[r-1]>=v[i][j])r--; val[r]=v[i][j];pos[r]=j;r++; if(pos[l]==j-n)l++; if(j>=n)mn[i][j]=val[l]; } } } void solve() { int ans=inf; int l,r; for(int i=n;i<=b;i++) { l=1,r=1; for(int j=1;j<=a;j++) { while(l<r&&val[r-1]>=mn[j][i])r--; val[r]=mn[j][i];pos[r]=j;r++; if(pos[l]==j-n)l++; if(j>=n)t1[j]=val[l]; } l=1,r=1; for(int j=1;j<=a;j++) { while(l<r&&val[r-1]<=mx[j][i])r--; val[r]=mx[j][i];pos[r]=j;r++; if(pos[l]==j-n)l++; if(j>=n)t2[j]=val[l]; } for(int i=n;i<=a;i++)ans=min(ans,t2[i]-t1[i]); } printf("%d\n",ans); } int main() { a=read();b=read();n=read(); for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) v[i][j]=read(); pre(); solve(); return 0; } |
计数器 9527556
OI 课件=>
OI 课件=>
这代码有bug..我还拍了半天