为了和谐

为了和谐

(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<cstdlib> using namespace std; struct node{int x,pos;}maxn[1001],minn[1001]; int h1,h2,t1,t2; int a[1001][1001],w[1001][1001],ww[1001][1001]; int main() { freopen("square.in","r",stdin); freopen("square.out","w",stdout); int aa,bb,n; scanf("%d%d%d",&aa,&bb,&n); for(int i=1;i<=aa;i++) { for(int j=1;j<=bb;j++) { scanf("%d",&a[i][j]); } } for(int j=1;j<=aa;j++) { h1=h2=1; t1=t2=0; for(int i=1;i<=bb;i++) { if(h1<=t1&&maxn[h1].pos<i-n+1) h1++; if(h2<=t2&&minn[h2].pos<i-n+1) h2++; while(h1<=t1&&maxn[t1].x<a[j][i])t1--; maxn[++t1].x=a[j][i];maxn[t1].pos=i; while(h2<=t2&&minn[t2].x>a[j][i])t2--; minn[++t2].x=a[j][i];minn[t2].pos=i; if(i-n+1>0) w[j][i-n+1]=maxn[h1].x,ww[j][i-n+1]=minn[h2].x; } } for(int j=1;j<=bb-n+1;j++) { h1=h2=1; t1=t2=0; for(int i=1;i<=aa;i++) { if(h1<=t1&&maxn[h1].pos<i-n+1) h1++; if(h2<=t2&&minn[h2].pos<i-n+1) h2++; while(h1<=t1&&maxn[t1].x<w[i][j])t1--; maxn[++t1].x=w[i][j];maxn[t1].pos=i; while(h2<=t2&&minn[t2].x>ww[i][j])t2--; minn[++t2].x=ww[i][j];minn[t2].pos=i; if(i-n+1>0) w[i-n+1][j]=maxn[h1].x,ww[i-n+1][j]=minn[h2].x; } } int ans=0x7fffffff; for(int i=1;i<=aa-n+1;i++) for(int j=1;j<=bb-n+1;j++) { if(w[i][j]-ww[i][j]<ans) ans=w[i][j]-ww[i][j]; } printf("%d",ans); }