[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
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2Sample Output
1一个显然结论:一个矩阵中最值一定是这个矩阵每行最值中的一个.
由于给定了我们矩阵大小,要求我们在线性的时间内求出所有区间最值,所以我们考虑使用单调队列.我们先处理好子矩阵每一行的最值,即一个数左边n个数中的最值.然后再竖着跑一下单调队列就可以了,其实主要是考察单调队列的熟练运用.思路并不难.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;#define id first
#define val secondtypedef pair<int,int> pii;static const int maxm=1e3+10;
static const int INF=~(1<<31);int v[maxm][maxm],mx[maxm][maxm],mn[maxm][maxm],Max[maxm],Min[maxm];
pii Q[maxm];
int head,tail,A,B,n;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",&v[i][j]);for(int i=1;i<=A;i++){head=1,tail=1;for(int j=1;j<=B;j++){while(head<=tail&&Q[tail].val<=v[i][j])tail--;Q[++tail].val=v[i][j];Q[tail].id=j;while(head<=tail&&Q[head].id<j-n+1)head++;if(j>=n)mx[i][j]=Q[head].val;}head=1,tail=1;for(int j=1;j<=B;j++){while(head<=tail&&Q[tail].val>=v[i][j])tail--;Q[++tail].val=v[i][j];Q[tail].id=j;while(head<=tail&&Q[head].id<j-n+1)head++;if(j>=n)mn[i][j]=Q[head].val;}}int ans=INF;for(int i=n;i<=B;i++){head=1,tail=1;for(int j=1;j<=A;j++){while(head<=tail&&Q[tail].val>=mn[j][i])tail--;Q[++tail].val=mn[j][i];Q[tail].id=j;while(head<=tail&&Q[head].id<j-n+1)head++;if(j>=n)Min[j]=Q[head].val;}head=1,tail=1;for(int j=1;j<=A;j++){while(head<=tail&&Q[tail].val<=mx[j][i])tail--;Q[++tail].val=mx[j][i];Q[tail].id=j;while(head<=tail&&Q[head].id<j-n+1)head++;if(j>=n)Max[j]=Q[head].val;}for(int j=n;j<=A;j++)ans=min(ans,Max[j]-Min[j]);}printf("%d\n",ans);return 0;
}传送门