2019牛客暑期多校训练营(第三场)- F Planting Trees

题目链接：https://ac.nowcoder.com/acm/contest/883/F

题意：给定n×n的矩阵，求最大子矩阵使得子矩阵中最大值和最小值的差值<=M。

思路：先看数据大小，注意题目说所有样例的N^3不超过25e7，意思就是我们可以用O(n^3)过题。

　　　最大子矩阵第二场出现过，做法是枚举上下边界实现降维，同时我们维护每一列的最大值最小值，然后枚举右边界，这时候复杂度已经为O(n^3)。那么左边界怎么确定呢？我们用两个单调队列维护子矩阵的最大值最小值，根据题目条件确定左边界，注意代码37、38行是if不是while（我想了好久。。QAQ），因为最多只需要从队首出一次（也就是将head+1，这个仔细想想就明白），用while没必要，而且while会出现段错误，如果这时候l=k，加一之后l=k+1，head1会超出tail，而里面的值不确定，可能导致死循环。

　　　总复杂度为O(n^3)。

AC代码：

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

int T,n,M,l,head1,tail1,head2,tail2,ans;

int a[maxn][maxn],Ma[maxn],Mi[maxn];

int q1[maxn],q2[maxn];

int main(){

    scanf("%d",&T);

    while(T--){

        ans=;

        scanf("%d%d",&n,&M);

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

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

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

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

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

                Ma[k]=Mi[k]=a[i][k];

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

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

                    Ma[k]=max(Ma[k],a[j][k]);

                    Mi[k]=min(Mi[k],a[j][k]);

                }

                l=,head1=head2=,tail1=tail2=;

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

                    while(tail1>=head1&&Ma[q1[tail1]]<=Ma[k])

                        --tail1;

                    while(tail2>=head2&&Mi[q2[tail2]]>=Mi[k])

                        --tail2;

                    q1[++tail1]=k;

                    q2[++tail2]=k;

                    while(l<=k&&Ma[q1[head1]]-Mi[q2[head2]]>M){

                        ++l;

                        if(q1[head1]<l) ++head1;

                        if(q2[head2]<l) ++head2;

                    }

                    ans=max(ans,(j-i+)*(k-l+));

                }

            }

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

2019牛客暑期多校训练营(第三场)- F Planting Trees

最新文章

热门文章