Description：

给定一个非负整数序列 $A$ ，每次操作可以选择一个数然后减掉 $1$ ，要求进行不超过 $m$ 次操作使得存在一个 $A_k=0$ 且 $\max(|A_i−A_{i+1}|)$ 最小，输出这个最小值以及此时最小的 $k$ 。

$1\le n \le 1000000$

Solution：

看到最大值最小想二分。

设二分的值是 $w$ ，首先无视 $A_k=0$ 的要求构造出一个满足 $\max(|A_i-A_{i+1}|)\le w$ 的解，可以先正着扫一遍，把 $A_i$ 更新为 $\min(A_i,A_{i-1}+w)$ ，然后反着同样做一遍，就得到了尽量少删数构造的合法方案，然后枚举每个位置作为 $k$ ，不难发现这个位置一定是一个山谷，山谷的两边是一个公差为 $w$ 的等差数列，那么如果知道了山谷最左边和最右边的位置加上前缀和就能计算出为了形成山谷删掉了多少数，由于 $\max(A_i,A_{i-1})\le w$ ，所以左右端点的位置都具有单调性，用两个双指针扫一下就能求出了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

int n;

ll m;

#define MAXN 1000010

#define INF 0x3f3f3f3f3f3f3f3f

int a[MAXN],b[MAXN];

ll tot;

ll sum[MAXN];

int pos;

bool check(int k)

{

    tot = 0;

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

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

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

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

    //for(int i = 1;i <= n;++i)cout << b[i] << " ";cout << endl;

    sum[0] = 0;

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

    ll ans = INF;

    pos = 0;

    for(int i = 1,l = 1,r = 1;i <= n;++i)

    {

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

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

        ll res = tot - (sum[n] - (sum[r] - sum[l - 1]));

        res -= ((ll)(1 + i - l) * (i - l) / 2 + (ll)(1 + r - i) * (r - i) / 2) * (ll)k;

        if(res < ans)

        {

            if(pos == 0 && res <= m)pos = i;

            ans = res;

        }//cout << i << " " << l << " " << r << " " << res << endl;

    }//cout << ans << endl;

    return (ans <= m);

}

int main()

{

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

    for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

    int l = 0,r = 1000000000,mid;

    while(l < r)

    {

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

        if(check(mid))r = mid;

        else l = mid + 1;

    }

    check(l);

    cout << pos << " " << l << endl;

    return 0;

}