题解 P3534 【[POI2012]STU-Well】

kczno1 · 2017-02-02 11:10:45 · 题解

题意应为使得max{|a(i)-a(i+1)|}最小。 二分答案del，

之后从后往前扫一遍，如果a(i)-a(i+1)>del就把a(i)减掉;

再从前往后扫一遍，如果a(i)-a(i-1)>del就把a(i)减掉。

现在考虑如何使得存在a(k)=0。

假如枚举k,那么使a(k)=0后，

相当于在(k,0)往左划了一条斜率=-del的直线，直线上方的都要被减掉。

肯定是从a(k-1)开始往前往后影响，影响到a(l);

同时往右划了一条斜率=del的直线，直线上方的都要被减掉。

肯定也是从a(k+1)开始持续到一个a(r)。

如果让这条直线单调往右，那么l,r也是单调往右的。

维护这个l,r即可。

#include<cstdio>

#define ll long long
#define N 1000100
int a0[N],a[N];ll s[N]; 
int n,i;ll m;

int ok(ll del)
{
    ll now=m,x;
    for (i=1;i<=n;++i) a[i]=a0[i];a[n+1]=-1;
    for (i=n-1;i;--i) 
    if ((x=a[i]-a[i+1]-del)>0)
    {
        a[i]-=x;now-=x;
    }
    if (now<0) return 0;
    for (i=2;i<=n;++i)
    if ((x=a[i]-a[i-1]-del)>0)
    {
        a[i]-=x;now-=x;
    }
    if (now<0) return 0;
    for (i=1;i<=n;++i) s[i]=s[i-1]+a[i];
    ll l=1,r=1;
    for (i=1;i<=n;++i)
    {
        x=a[i];a[i]=0;
        while (a[l]<del*(i-l)) ++l;
        while (a[r+1]>=del*(r+1-i)) ++r;
        a[i]=x;
        if (s[r]-s[l-1]-now<=(del*((i-l)*(i-l+1)+(r-i)*(r-i+1)>>1))) return i;    
    }
    return 0;
}

int main()
{
    freopen("1.in","r",stdin);
    scanf("%d%lld",&n,&m);
    for (i=1;i<=n;++i) scanf("%d",a0+i);
    if (ok(0)) {printf("%d %d",ok(0),0);return 0;}
    int l=0,r=1e9+1;
    while (l+1!=r)//l is false r is ok
    {
        int mid=l+r>>1;
        if (ok(mid)) r=mid;
        else l=mid;
    }
    printf("%d %d",ok(r),r);
}