[BZOJ]1047: [HAOI2007]理想的正方形

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

Sample Output

1

用两次单调队列，第一次求出每行每n个数的最大最小值，第二次把第一次的量看作一个整体，竖着来一次单调队列，就搞定了。

代码：

#include
#include
const int Q=1002;
int r,c,n,a[Q][Q];
struct tyb {int id,x;};
int Max[Q][Q],Min[Q][Q],ans=2147483647;
int main()
{scanf("%d%d%d",&r,&c,&n);for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)scanf("%d",&a[i][j]);for(int i=1;i<=r;i++){tyb q[Q];int st=1,ed=0;for(int j=1;j<=n;j++){while(st<=ed && a[i][j]>=q[ed].x) ed--;ed++;q[ed].x=a[i][j];q[ed].id=j;}Max[i][n]=q[st].x;for(int j=n+1;j<=c;j++){while(st<=ed && a[i][j]>=q[ed].x) ed--;ed++;q[ed].x=a[i][j];q[ed].id=j;while(st<=ed && q[st].id=q1[ed1].x) ed1--;ed1++;q1[ed1].x=Max[i][j];q1[ed1].id=i;/***********************************************/while(st2<=ed2 && Min[i][j]<=q2[ed2].x) ed2--;ed2++;q2[ed2].x=Min[i][j];q2[ed2].id=i;}if(q1[st1].x-q2[st2].x=q1[ed1].x) ed1--;ed1++;q1[ed1].x=Max[i][j];q1[ed1].id=i;while(st1<=ed1 && q1[st1].id

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！