BZOJ1047: [HAOI2007]理想的正方形 [单调队列]

1047: [HAOI2007]理想的正方形

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2857 Solved: 1560
[Submit][Status][Discuss]

Description

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

Input

　　第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每
行相邻两数之间用一空格分隔。
100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100

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 2

Sample Output

竟然1A了

区间最大值和最小值，想到单调队列

考虑降维，把一列上n个数压成一个数，然后一行一行做

也就是先竖着每一列用单调队列分别处理mx[i][j]为(i,j)向上n个中最大的，mn[i][j]同理

然后一行一行处理f[j]此行j往前n个中mx最大值，g是mn最小值

对于能够成矩形的更新ans就行了

PS：注意初始值问题

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1005,INF=2e9+5;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n,m,k,a[N][N];
int mx[N][N],mn[N][N];
int q[N],head=1,tail=0;
void handle(int c){//printf("handle %d
",c);
    head=1;tail=0;
    for(int i=1;i<=n;i++){
        while(head<=tail&&q[head]<=i-k) head++;
        while(head<=tail&&a[i][c]>a[q[tail]][c]) tail--;
        q[++tail]=i;
        mx[i][c]=max(mx[i][c],a[q[head]][c]);
    }
    
    head=1;tail=0;
    for(int i=1;i<=n;i++){
        while(head<=tail&&q[head]<=i-k) head++;//if(c==1)printf("head %d %d
",head,q[head]);
        while(head<=tail&&a[i][c]<a[q[tail]][c]) tail--;
        q[++tail]=i;//if(c==1)printf("tail %d %d
",tail,q[tail]);
        mn[i][c]=min(mn[i][c],a[q[head]][c]);//if(c==1)printf("mn %d %d %d
",i,c,mn[i][c]);
    }
}
int f[N],g[N],ans=INF;
void sol(int r){
    head=1;tail=0;
    memset(f,0,sizeof(f));
    for(int j=1;j<=m;j++){
        while(head<=tail&&q[head]<=j-k) head++;
        while(head<=tail&&mx[r][j]>mx[r][q[tail]]) tail--;
        q[++tail]=j;
        f[j]=max(f[j],mx[r][q[head]]);
    }
    
    head=1;tail=0;
    memset(g,127,sizeof(g));
    for(int j=1;j<=m;j++){
        while(head<=tail&&q[head]<=j-k) head++;
        while(head<=tail&&mn[r][j]<mn[r][q[tail]]) tail--;
        q[++tail]=j;
        g[j]=min(g[j],mn[r][q[head]]);
    }
    
    for(int j=k;j<=m;j++) ans=min(ans,f[j]-g[j]);//,printf("sol %d %d %d %d
",r,j,f[j],g[j]);
}
int main(){
    n=read();m=read();k=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            a[i][j]=read();
        }
    
    memset(mn,127,sizeof(mn));
    for(int j=1;j<=m;j++) handle(j);
    for(int i=k;i<=n;i++) sol(i);
    printf("%d",ans);
    
//    cout<<"test
";
//    for(int i=1;i<=n;i++)
//        for(int j=1;j<=m;j++) printf("%d %d %d %d
",i,j,mx[i][j],mn[i][j]);
}