2019 牛客暑期多校 第三场 F Planting Trees (单调队列+尺取)

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

题意:求一个矩阵最大面积,这个矩阵的要求是矩阵内最小值与最大值差值<=m

思路:首先我们仔细观察范围,我们就知道可以n^3,前面这题我(看付队博客)讲过求一个最大的什么矩阵就是分两种情况,

第一种:枚举上下边界,转化为一维,复杂度n^3

第二种:枚举下边界,转化为高楼问题,复杂度n^2

 

这里显然复杂度可以n^3,我们就想一下三场循环,这题实际上就是找到矩阵内的最大值最小值

第一层肯定是枚举上边界

第二层我们要边枚举下边界边求当前列的最大最小值

第三层 这里其实也就是转化为了一个一维的题,求一个序列内,每个有一个最大最小值,任意两点差值不超过m,然后问最大连续长度是多少

这个其实很简单,我们用两个单调队列分别记录最大最小值,然后尺取过去即可,这里必须手动模拟队列,不然会超时。(亲测)

附:我们第一层枚举上边界,第二层枚举下边界是有特殊原因的,这样方便O(n)求出所有最大值

2019 牛客暑期多校  第三场  F  Planting Trees (单调队列+尺取)
#include<bits/stdc++.h>
#define maxn 505
#define mod 1000000007
using namespace std;
typedef long long ll;
ll n,m;
ll mp[maxn][maxn];
ll mx[maxn],mn[maxn];
ll qn[maxn],qx[maxn];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld",&n,&m);
        ll ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%lld",&mp[i][j]);
            }
        } 
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                mx[j]=-mod;
                mn[j]=mod;
            }
            for(int j=i;j<=n;j++){
                for(int k=1;k<=n;k++){
                    mx[k]=max(mx[k],mp[j][k]);
                    mn[k]=min(mn[k],mp[j][k]);
                } 
                ll l=1,r=1,f1=1,f2=1,b1=0,b2=0;
                while(r<=n){
                    while(f1<=b1&&mx[r]>=mx[qx[b1]]) b1--;
                    qx[++b1]=r;
                    while(f2<=b2&&mn[r]<=mn[qn[b2]]) b2--;
                    qn[++b2]=r;
                    if(mx[qx[f1]]-mn[qn[f2]]<=m){
                        ans=max((r-l+1)*(j-i+1),ans);
                        r++;
                        continue;
                    }
                    ans=max((r-l)*(j-i+1),ans);
                    while(l<=r&&mx[qx[f1]]-mn[qn[f2]]>m){
                        l++;
                        while(f1<=b1&&qx[f1]<l) f1++;
                           while(f2<=b2&&qn[f2]<l) f2++;
                    }
                    r++;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}
View Code

 

上一篇:[USACO11DEC]牧草种植Grass Planting


下一篇:负载均衡算法(待续)