bzoj 2792 [Poi2012]Well 二分+dp+two_pointer

题目大意

给出n个正整数X1,X2,...Xn，可以进行不超过m次操作，每次操作选择一个非零的Xi，并将它减一。

最终要求存在某个k满足Xk=0，并且z=max{|Xi - Xi+1|}最小。

输出最小的z和此时最小的k。

第一行两个正整数n, m (1<=n<=1,000,000, 1<=m<=10^18)。第二行n个正整数X1,X2,...Xn (Xi<=10^9)。

分析

我们考虑简单点的问题

我们要最小化z，考虑二分

对于没有要求变成0的问题

我们会尽可能使每个数操作后最大

因为没有+1操作

两个数相差大于mid时

只能大的数减下去

b[i]表示每个数最大是多少

从左往右扫一次,\(b[i]=min(b[i],b[i-1]+mid)\)

从右往左扫一次,\(b[i]=min(b[i],b[i+1]+mid)\)

然后我们枚举将哪一个数变成0

设枚举到i

我们只用找到最大的L满足\(b[L]<=(i-L)*mid\)

找到最小的R满足\(b[R]<=(R-i)*mid\)

此时（L，R）中的数一定要修改

修改成等差数列

稍微想一想可以证明此时对区间外的数没有任何影响

右注意到随着i增加，L-R区间也单调右移

two-pointer一下

solution

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cmath>

#include <algorithm>

typedef long long LL;

using namespace std;

const int M=1000007;

int n;

LL lim,ss=0;

int a[M];

int b[M];

LL s[M];

LL calc(LL d,LL l){

    return d*(l*(l+1)/2);

}

int check(int del){

    LL c1=0,c2=0;

    int i;

    for(i=1;i<=n;i++) b[i]=a[i];

    for(i=2;i<=n;i++) b[i]=min(b[i],b[i-1]+del);

    for(i=n-1;i>0;i--) b[i]=min(b[i],b[i+1]+del);

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

        c1+=a[i]-b[i];

        s[i]=b[i]+s[i-1];

    }

    if(c1>lim) return 0;

    int l=1,r=2;

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

        while(l<i&&b[l]<=(i-l)*del) l++;

        while(r<=n&&b[r]>(r-i)*del) r++;

        c2=s[r-1]-s[l-1];

        c2-=calc(del,i-l);

        c2-=calc(del,r-1-i);

        if(c1+c2<=lim) return i;

    }

    return 0;

}

void solve(){

    if(ss<=lim) {printf("1 0\n");return;}

    int res=0,tp;

    int l=1,r=1000000000,mid;

    while(l<r){

        mid=l+r>>1;

        tp=check(mid);

        if(tp){

            r=mid;

            res=tp;

        }

        else l=mid+1;

    }

    printf("%d %d\n",res,l);

}

inline int rd(){

    int x=0;bool f=1;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

    for(;isdigit(c);c=getchar()) x=x*10+c-48;

    return f?x:-x;

}

int main(){

    int i;

    scanf("%d%lld",&n,&lim);

    for(i=1;i<=n;i++) a[i]=rd(),ss+=a[i];

    solve();

    return 0;

}