美文网首页
【单调栈】【前缀和】【二分查找】8.28题解-long

【单调栈】【前缀和】【二分查找】8.28题解-long

作者: bbqub | 来源:发表于2017-08-29 15:31 被阅读0次

    long


    题目描述

    AP神牛准备给自己盖一座很华丽的宫殿。于是,他看中了一块N*M的矩形空地。空地中每个格子都有自己的海拔高度。AP想让他的宫殿的平均海拔在海平面之上(假设海平面的高度是0,平均数都会算吧?)。而且,AP希望他的宫殿尽量大,能够容纳更多的人来膜拜他。请问AP的宫殿最后会有多大?

    输入输出

    输入
    第一行为N和M。之后N行,每行M个数,描述的空地的海拔。
    输出
    输出一行,表示宫殿最大面积。

    样例

    样例输入

    3 2
    4 0
    -10 8
    -2 -2
    

    样例输出

    4
    

    说明

    数据范围
    对于30%的数据,N,M≤50;
    对于100%的数据,N,M≤200;

    思路

    1. 用前缀和a[i][j]表示第i行1~j列的和
    2. 开一个单调栈,存海拔之和
    3. a[k][j]-a[k][q]代表第k行第q列到第j列的海拔高度和
    4. 当s<0时,设s=p (p<0),在栈中寻找p所对应的f[p],
    5. 用当前行数k减去f[p],即可得到一段平均海拔在海平面之上的区间。

    代码

    #include<cstdio>
    #include<iostream>
    using namespace std;
    long long n,m,x,a[201][201],f[201],sta[201],size,ans;
    inline long long erfen(long long u) {
        long long l=1,r=size,tot=-1;
        while(l<=r) {
            long long mid=(l+r)>>1;
            if(sta[mid]<u) {
                r=mid-1;
                tot=mid;
            } else l=mid+1;
        }
        return tot;
    }
    inline int read() {
        long long x=0,w=1;
        char ch=0;
        while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
        if(ch=='-') w=-1,ch=getchar();
        while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
        return x*w;
    }
    int main() {
        freopen("long.in","r",stdin);
        freopen("long.out","w",stdout);
        n=read();
        m=read();
        for(long long i=1; i<=n; i++)
            for(long long j=1; j<=m; j++) {
                x=read();
                a[i][j]=a[i][j-1]+x;
            }
        for(long long i=1; i<=m; i++)
            for(long long j=1; j<=m; j++) {
                long long s=0;
                sta[0]=1e10;
                size=0;
                for(long long k=1; k<=n; k++) {
                    s+=a[k][j]-a[k][i-1];
                    if(s>0) ans=max(ans,k*(j-i+1));
                    else {
                        int z=erfen(s);
                        if(z!=-1) ans=max(ans,(j-i+1)*(k-f[z]));
                    }
                    if(sta[size]>s) sta[++size]=s,f[size]=k;
                }
            }
        printf("%lld\n",ans);
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:【单调栈】【前缀和】【二分查找】8.28题解-long

          本文链接:https://www.haomeiwen.com/subject/ewiodxtx.html