BZOJ_2792_[Poi2012]Well_二分答案

2023-10-10 09:16:58

Description

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

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

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

Input

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

Output

输出k和z。数据保证方案一定存在。

Sample Input

16 15
8 7 6 5 5 5 5 5 6 6 7 8 9 7 5 5

Sample Output

1 2

HINT

将X序列变为

0 2 4 5 5 5 5 5 6 6 7 8 9 7 5 5

此时k=1，z=2，共操作了8+5+2=15次。

分析：首先肯定要二分答案出z，然后转化为判定是否能用小于等于m次操作使序列满足题意。

假设把第一个位置变成零，那么贪心的让后面比前面高度正好大z，扫一遍即可，可以发现最后的序列有若干个等差数列。

然后考虑怎么推出把其他位置i变成零对答案的贡献，i右边的数会下去一些，i左边的数会上去一些，可以发现这个满足单调性。

设f[i]为把第i个数变为0，左边需要改多少次，g[i]表示右边需要改多少次，双指针扫一遍，找到第一个大于|(j-i)|*z的位置，算出贡献即可。

有个小问题，可能序列一开始是不合法的，这是我们要从左往右再从右往左扫一遍，把不合法的部分削掉。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 1000050

typedef long long ll;

int n,a[N],b[N],maxx;

ll m,s[N],f[N],g[N];

int check(int p) {

    ll re=0;

    int i,j;

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

    for(int i=2;i<=n;i++)

        if(b[i]-b[i-1]>p)

            re+=b[i]-b[i-1]-p,b[i]=b[i-1]+p;

    for(int i=n-1;i;i--)

        if(b[i]-b[i+1]>p)

            re+=b[i]-b[i+1]-p,b[i]=b[i+1]+p;

    if(re>m) return 0;

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

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

        while(j<i&&b[j]<=1ll*(i-j)*p) j++;

        f[i]=s[i-1]-s[j-1]-1ll*(i-j)*(i-j+1)/2*p;

    }

    for(i=n,j=n;i;i--) {

        while(j>i&&b[j]<=1ll*(j-i)*p) j--;

        g[i]=s[j]-s[i]-1ll*(j-i)*(j-i+1)/2*p;

    }

    for(i=1;i<=n;i++) if(f[i]+g[i]+b[i]+re<=m) return i;

    return 0;

}

int main() {

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

    int i;

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

        scanf("%d",&a[i]);

        maxx=max(maxx,a[i]);

    }

    int l=0,r=maxx+1;

    while(l<r) {

        int mid=(l+r)>>1;

        if(check(mid)) r=mid;

        else l=mid+1;

    }

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

}