luogu2216&bzoj1047 [HAOI2007]理想的正方形

luogu2216&bzoj1047 [HAOI2007]理想的正方形

​​ 题目描述

有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

输入输出格式

输入格式：

第一行为3个整数，分别表示a,b,n的值

第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。

输出格式：

仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。

输入输出样例

输入样例#1： 复制

5 4 2 1 2 5 6 0 17 16 0 16 17 2 1 2 10 2 1 1 2 2 2 输出样例#1： 复制

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

单调队列搞 对于每一个矩形的前n列均暴力重建

我针对每一列都建立单调队列 q3[j]q4[j] 表示第j列的递增和递减单调队列

q1 q2表示这一行的递增和递减单调队列 注意:要将竖着的一列的值和map[i][j]做比较 然后再做q1和q2 这两个单调队列

#include#define N 1100#define inf 0x7f7f7f7f#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}struct node{ int x,y,v;};//q1->max q2->min q3->max q4->minint map[N][N],a,b,n;deque q1,q2,q3[N],q4[N]; int main(){ freopen("2216.in","r",stdin); a=read();b=read();n=read();int ans=inf; for (int i=1;i<=a;++i) for (int j=1;j<=b;++j) map[i][j]=read(); int op1=1,cl1=0,op2=1,cl2=0; for (int k=1;k<=b-n+1;++k){ int min1=inf,max1=0; for (int j=k;j<=k+n-1;++j){ for (int i=1;i<=n;++i){ while (!q3[j].empty()&&q3[j].back().vmap[i][j]) q4[j].pop_back(); max1=max(max1,map[i][j]);min1=min(min1,map[i][j]); node tmp;tmp.v=map[i][j];tmp.x=i;tmp.y=j;q3[j].push_back(tmp);q4[j].push_back(tmp); } }ans=min(ans,max1-min1); } for (int i=n+1;i<=a;++i){ q1.clear();q2.clear(); for (int j=1;j<=n;++j){ while (!q3[j].empty()&&q3[j].front().x<=i-n) q3[j].pop_front(); while (!q4[j].empty()&&q4[j].front().x<=i-n) q4[j].pop_front(); while (!q3[j].empty()&&q3[j].back().vmap[i][j]) q4[j].pop_back(); node tmp;tmp.v=map[i][j];tmp.x=i;tmp.y=j;node max2,min2;max2.v=0;min2.v=inf; q3[j].push_back(tmp);q4[j].push_back(tmp);max2.x=i;max2.y=j;min2.x=i;min2.y=j;max2.v=min2.v=map[i][j]; if (q4[j].front().vmax2.v) {max2.v=q3[j].front().v;max2.x=q3[j].front().x;max2.y=q3[j].front().y;} while (!q1.empty()&&q1.back().vmin2.v) q2.pop_back(); q1.push_back(max2);q2.push_back(min2); } for (int j=1;j<=n;++j) ans=min(ans,max(q1.front().v,q3[j].front().v)-min(q2.front().v,q4[j].front().v)); for (int j=n+1;j<=b;++j){ while (!q3[j].empty()&&q3[j].front().x<=i-n) q3[j].pop_front(); while (!q4[j].empty()&&q4[j].front().x<=i-n) q4[j].pop_front(); while (!q3[j].empty()&&q3[j].back().vmap[i][j]) q4[j].pop_back(); node tmp;tmp.v=map[i][j];tmp.x=i;tmp.y=j;node max2,min2;max2.v=0;min2.v=inf; q3[j].push_back(tmp);q4[j].push_back(tmp);max2.x=i;max2.y=j;min2.x=i;min2.y=j;max2.v=min2.v=map[i][j]; if (q4[j].front().vmax2.v) {max2.v=q3[j].front().v;max2.x=q3[j].front().x;max2.y=q3[j].front().y;} while (!q1.empty()&&q1.front().y<=j-n) q1.pop_front(); while (!q2.empty()&&q2.front().y<=j-n) q2.pop_front(); while (!q1.empty()&&q1.back().vmin2.v) q2.pop_back(); q1.push_back(max2);q2.push_back(min2); ans=min(ans,max(q1.front().v,q3[j].front().v)-min(q2.front().v,q4[j].front().v)); } }printf("%d",ans); return 0;

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。