题解 P1714 【切蛋糕】

Dream_It_Possible · 2018-04-11 23:29:12 · 题解

这题一眼扫过，第一感觉——最大子段和，但n^2算法显然会超时，我们可以做一个前缀和，维护1~i的和，这样就可得出：

MAX=max(MAX,s[i]-min{s[j]});

注: j范围为: i-m~i-1

也就是求i~j的最大和。

由于n太大，要用数据结构维护，我用的是线段树，维护前缀和。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct Tree{

    int l, r;
    long long sum;
    int mxa,mni;
} tr[2000005]; //要开四倍 
int a[500000],sum[500005];//sum[i]记录1~i的前缀和
inline void read(int &a)//快读
{
    int k=1; a=0; char c=getchar();
    while(c<'0'||'9'<c){if(c=='-')k=-1; c=getchar();}
    while('0'<=c&&c<='9'){a=a*10+c-'0'; c=getchar();}
    a*=k;
}
void build(int x,int y,int i) //建树-->build(1,n,1) 
{

    tr[i].l=x;
    tr[i].r=y;
    if(x==y)
    tr[i].sum=tr[i].mxa=tr[i].mni=sum[x];
    else
    {
        long long mid=(tr[i].l+tr[i].r)/2;
        build(x,mid,i*2);
        build(mid+1,y,i*2+1);
        tr[i].sum=tr[i*2].sum+tr[i*2+1].sum; 
        tr[i].mxa=max(tr[2*i].mxa,tr[2*i+1].mxa);
        tr[i].mni=min(tr[2*i].mni,tr[2*i+1].mni);
    }
}
void change(int q,int val,int i) //将q变成val （这里没用）
{
    if(tr[i].l==q&&tr[i].r==q)
    {
        tr[i].sum=tr[i].mxa=tr[i].mni=val;
    }
    else
    {
        long long mid=(tr[i].l+tr[i].r)/2;
        if (q<=mid)
        {
            change(q,val,i*2);
        }
        else if(q>mid)
        {
            change(q,val,i*2+1);
        }
        tr[i].sum=tr[i*2].sum+tr[i*2+1].sum;
        tr[i].mxa=max(tr[2*i].mxa,tr[2*i+1].mxa);
        tr[i].mni=min(tr[2*i].mni,tr[2*i+1].mni);
    }
}
long long query(int l,int r,int i)//求从l到r的和 （这里没用）
{
    if (l<=tr[i].l&&r>=tr[i].r) 
    return tr[i].sum;
    else
    {
        long long mid=(tr[i].l+tr[i].r)/2;
        if(l>mid) 
        {
            return query(l,r,i*2+1);
        }
        else if (r<=mid) 
        {
            return query(l,r,i*2);
        }
        else
        {
            return query(l,r,i*2)+query(l,r,i*2+1);
        }
    }
}
long long find_mni(int l,int r,int u)//求l到r的最小值 
{
    if (tr[u].l==l&&tr[u].r==r)
    {
        return tr[u].mni;
    }
    long long mid=(tr[u].l+tr[u].r)/2;
    if (mid>=r)
    {
        return find_mni(l,r,u*2);
    }
    else
    if (mid<l)
    {
        return find_mni(l,r,u*2+1);
    }
    else
    {
        return min(find_mni(l,mid,u*2),find_mni(mid+1,r,u*2+1));
    }
}
long long find_mxa(int l,int r,int u)//求l到r的最大值 （这里没用） 
{
    if (tr[u].l==l&&tr[u].r==r)
    {
        return tr[u].mxa;
    }
    long long mid=(tr[u].l+tr[u].r)/2;
    if (mid>=r)
    {
        return find_mxa(l,r,u*2);
    }
    else
    if (mid<l)
    {
        return find_mxa(l,r,u*2+1);
    }
    else
    {
        return max(find_mxa(l,mid,u*2),find_mxa(mid+1,r,u*2+1));
    }
}
int main()
{
    int n,m,i,j;
    cin>>n>>m; 
    for (i=1;i<=n;i++)
    {
        read(a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    build (1,n,1);
    long long mxa=-1;
    for (i=m+1;i<=n;i++)
    {
        mxa=max(mxa,sum[i]-find_mni(i-m,i-1,1));记录最大值
    }
    cout<<mxa;
    return 0;
}