首页 > 代码库 > BZOJ1047: [HAOI2007]理想的正方形 [单调队列]
BZOJ1047: [HAOI2007]理想的正方形 [单调队列]
1047: [HAOI2007]理想的正方形
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 2857 Solved: 1560
[Submit][Status][Discuss]
Description
有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值
的差最小。
Input
第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每
行相邻两数之间用一空格分隔。
100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100
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
竟然1A了
区间最大值和最小值，想到单调队列
考虑降维，把一列上n个数压成一个数，然后一行一行做
也就是先竖着每一列用单调队列分别处理mx[i][j]为(i,j)向上n个中最大的，mn[i][j]同理
然后一行一行处理f[j]此行j往前n个中mx最大值，g是mn最小值
对于能够成矩形的更新ans就行了
PS：注意初始值问题
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int N=1005,INF=2e9+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m,k,a[N][N];int mx[N][N],mn[N][N];int q[N],head=1,tail=0;void handle(int c){//printf("handle %d\n",c); head=1;tail=0; for(int i=1;i<=n;i++){ while(head<=tail&&q[head]<=i-k) head++; while(head<=tail&&a[i][c]>a[q[tail]][c]) tail--; q[++tail]=i; mx[i][c]=max(mx[i][c],a[q[head]][c]); } head=1;tail=0; for(int i=1;i<=n;i++){ while(head<=tail&&q[head]<=i-k) head++;//if(c==1)printf("head %d %d\n",head,q[head]); while(head<=tail&&a[i][c]<a[q[tail]][c]) tail--; q[++tail]=i;//if(c==1)printf("tail %d %d\n",tail,q[tail]); mn[i][c]=min(mn[i][c],a[q[head]][c]);//if(c==1)printf("mn %d %d %d\n",i,c,mn[i][c]); }}int f[N],g[N],ans=INF;void sol(int r){ head=1;tail=0; memset(f,0,sizeof(f)); for(int j=1;j<=m;j++){ while(head<=tail&&q[head]<=j-k) head++; while(head<=tail&&mx[r][j]>mx[r][q[tail]]) tail--; q[++tail]=j; f[j]=max(f[j],mx[r][q[head]]); } head=1;tail=0; memset(g,127,sizeof(g)); for(int j=1;j<=m;j++){ while(head<=tail&&q[head]<=j-k) head++; while(head<=tail&&mn[r][j]<mn[r][q[tail]]) tail--; q[++tail]=j; g[j]=min(g[j],mn[r][q[head]]); } for(int j=k;j<=m;j++) ans=min(ans,f[j]-g[j]);//,printf("sol %d %d %d %d\n",r,j,f[j],g[j]);}int main(){ n=read();m=read();k=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ a[i][j]=read(); } memset(mn,127,sizeof(mn)); for(int j=1;j<=m;j++) handle(j); for(int i=k;i<=n;i++) sol(i); printf("%d",ans); // cout<<"test\n";// for(int i=1;i<=n;i++)// for(int j=1;j<=m;j++) printf("%d %d %d %d\n",i,j,mx[i][j],mn[i][j]);}
BZOJ1047: [HAOI2007]理想的正方形 [单调队列]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。