发个昨天考试的题 二维单调队列 单调队列之前也学了但没做过题，没写过。但我感觉也不难，今天直接搞了个二维的； 发个一维的讲解，不会的先看一下，以便看懂下面的题解。点这里 T1 为了和谐 (square.pas/c/cpp) [问题背景] 在机房里，有两只小可爱，一只大可爱，一只小可爱。其中大可 爱对大的东西感兴趣，小可爱对小的东西感兴趣。 现在有一个 a*b 的矩阵，矩阵中每个位置都有一个非负整数 i （ 0<=i<=2000 000 000），两只小可爱要在这个矩阵中选择一个 n*n 的 正方形，大可爱要正方形中的最大数，小可爱要正方形中的最小数。 但是，如果两个人的数字差距过大的话，就会造成矛盾……为了 机房人民的和谐相处，请你帮他们选择这个正方形，使得这个差距最 小。 [问题描述] 有一个 a*b 的整数组成的矩阵，现请你从中找出一个 n*n 的正 方形区域，使得该区域所有数中的最大值和最小值的差最小。 INPUT (square.in) 第一行 3 个整数 a b n 接下来 a 行，每行 b 个非负整数。 OUTPUT (square.out) 仅一个整数，表示正方形中最大数与最小数之差[样例输入] 5 4 2 1 2 5 6 0 17 16 0 16 17 2 1 2 10 2 1 1 2 2 2 [样例输出] 1 HINT 1， 矩阵中所有数小于 2000 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
先每行搞单调队列，一个最大一个最小。然后对应存起来这个位置区间的最值。再按列搞，搞出来就是矩阵的最值。 代码
#include<iostream>#include<cstdio>#include<cstring>#define N 1010using namespace std;struct M{ int pos,x;}maxn[N],minn[N];int mar[N][N],ma[N][N],mi[N][N],n,a,b,ha,hi,ta,ti,ans;int main(){ freopen("square.in","r",stdin); freopen("square.out","w",stdout); scanf("%d%d%d",&a,&b,&n); for(int i=1;i<=a;++i) for(int j=1;j<=b;++j)scanf("%d",&mar[i][j]); for(int i=1;i<=a;++i) { ha=hi=1;ta=ti=0; for(int j=1;j<=b;++j) { if(ha<=ta&&maxn[ha].pos<j-(n-1))ha++; if(hi<=ti&&minn[hi].pos<j-(n-1))hi++; while(ha<=ta&&mar[i][j]>maxn[ta].x)ta--; maxn[++ta].x=mar[i][j],maxn[ta].pos=j; while(hi<=ti&&mar[i][j]<minn[ti].x)ti--; minn[++ti].x=mar[i][j],minn[ti].pos=j; if(j-(n-1)>0)ma[i][j-(n-1)]=maxn[ha].x, mi[i][j-(n-1)]=minn[hi].x; } } for(int j=1;j<=b-(n-1);++j) { ha=hi=1;ta=ti=0; for(int i=1;i<=a;++i) { if(ha<=ta&&maxn[ha].pos<i-(n-1))ha++; if(hi<=ti&&minn[hi].pos<i-(n-1))hi++; while(ha<=ta&&ma[i][j]>maxn[ta].x)ta--; maxn[++ta].x=ma[i][j],maxn[ta].pos=i; while(hi<=ti&&mi[i][j]<minn[ti].x)ti--; minn[++ti].x=mi[i][j],minn[ti].pos=i; if(i-(n-1)>0)ma[i-(n-1)][j]=maxn[ha].x, mi[i-(n-1)][j]=minn[hi].x; } } ans=0x7fffffff; for(int i=1;i<=a-(n-1);++i) for(int j=1;j<=b-(n-1);++j) ans=min(ans,ma[i][j]-mi[i][j]); PRintf("%d",ans); return 0; }新闻热点
疑难解答
