LG2216 理想的正方形

题意

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

思路

对于每一列，都用两个单调队列维护最大值和最小值，然后让我们一行一行的改变它

一行的列单调队列维护完之后，我们再拿出两个单调队列，对\(b\)个列最大值和列最小值求最大值和最小值

口糊真是太容易了，所以就可以写一份极繁的代码

#include <bits/stdc++.h>

using std::min;

const int N=1005;

int m,n,s,a[N][N],h[N],h2[N],t[N],t2[N],tmax[N],tmin[N],amax[N][N],amin[N][N],ans=1000000000;

int main(){

    scanf("%d%d%d",&n,&m,&s);

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

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

            scanf("%d",&a[i][j]);

    for (int i=1;i<=m;i++) h[i]=h2[i]=1;

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

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

            if (amax[j][h[j]]<=i-s) ++h[j];

            if (amin[j][h2[j]]<=i-s) ++h2[j];

            while (a[i][j]>=a[amax[j][t[j]]][j] && t[j]>=h[j]) --t[j];

            while (a[i][j]<=a[amin[j][t2[j]]][j] && t2[j]>=h2[j]) --t2[j];

            amax[j][++t[j]]=i,amin[j][++t2[j]]=i; 

        }

        if (i>=s) {

            int tail2=0,tail1=0,head=1,head2=1;

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

                if (tmax[head]<=j-s) ++head;

                if (tmin[head2]<=j-s) ++head2;

                while (a[amax[j][ h[j]]][j]>=a[amax[tmax[tail1]][h[tmax[tail1]]]][tmax[tail1]] && tail1>=head) --tail1;

                while (a[amin[j][h2[j]]][j]<=a[amin[tmin[tail2]][h2[tmin[tail2]]]][tmin[tail2]] && tail2>=head2) --tail2;

                tmax[++tail1]=j,tmin[++tail2]=j;

                if (tail1>=head && tail2>=head2 && j>=s)

                ans=min(ans,a[amax[tmax[head]][h[tmax[head]]]][tmax[head]]-a[amin[tmin[head2]][h2[tmin[head2]]]][tmin[head2]]);

            }

        }

    }

    printf("%d",ans);

}

注意一下两个指针的循环条件

巴特西

LG2216 理想的正方形

题意

思路

最新文章

热门文章