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=,INF=2e9+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,k,a[N][N];

int mx[N][N],mn[N][N];

int q[N],head=,tail=;

void handle(int c){//printf("handle %d\n",c);

    head=;tail=;

    for(int i=;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=;tail=;

    for(int i=;i<=n;i++){

        while(head<=tail&&q[head]<=i-k) head++;//if(c==1)printf("head %d %d\n",head,q[head]);

        while(head<=tail&&a[i][c]<a[q[tail]][c]) tail--;

        q[++tail]=i;//if(c==1)printf("tail %d %d\n",tail,q[tail]);

        mn[i][c]=min(mn[i][c],a[q[head]][c]);//if(c==1)printf("mn %d %d %d\n",i,c,mn[i][c]);

    }

}

int f[N],g[N],ans=INF;

void sol(int r){

    head=;tail=;

    memset(f,,sizeof(f));

    for(int j=;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=;tail=;

    memset(g,,sizeof(g));

    for(int j=;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\n",r,j,f[j],g[j]);

}

int main(){

    n=read();m=read();k=read();

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++){

            a[i][j]=read();

        }

    memset(mn,,sizeof(mn));

    for(int j=;j<=m;j++) handle(j);

    for(int i=k;i<=n;i++) sol(i);

    printf("%d",ans);

//    cout<<"test\n";

//    for(int i=1;i<=n;i++)

//        for(int j=1;j<=m;j++) printf("%d %d %d %d\n",i,j,mx[i][j],mn[i][j]);

}

秒客网