题目大意：给定一个非负整数序列A。每次操作能够选择一个数然后减掉1，要求进行不超过m次操作使得存在一个Ak=0且max{Ai−Ai+1}最小，输出这个最小值以及此时最小的k

二分答案，然后验证的时候首先让相邻的都不超过x。然后枚举哪个点应该改成0

假设某个点须要改成0，那么须要进行操作的位置是一段区间。左右端点都单调，扫两遍即可了

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define M 1001001

using namespace std;

int n,pos,a[M];

long long m;

bool Judge(long long limit)

{

    long long cost=0;

    int i,j;

    static int b[M];

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

        b[i]=a[i];

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

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

        {

            cost+=b[i]-b[i-1]-limit;

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

        }

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

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

        {

            cost+=b[i]-b[i+1]-limit;

            b[i]=b[i+1]+limit;

        }

    if(cost>m) return false;

    static long long sum[M];

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

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

    static int l[M],r[M];

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

    {

        while( b[j]<(long long)(i-j)*limit )

            j++;

        l[i]=j;

    }

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

    {

        while( b[j]<(long long)(j-i)*limit )

            j--;

        r[i]=j;

    }

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

    {

        long long _cost=(sum[r[i]]-sum[l[i]-1]);

        _cost-=(long long)limit*(i-l[i])*(i-l[i]+1)>>1;

        _cost-=(long long)limit*(r[i]-i)*(r[i]-i+1)>>1;

        if(cost+_cost<=m)

            return pos=i,true;

    }

    return false;

}

int Bisection()

{

    int l=0,r=1000000000;

    while(r-l>1)

    {

        int mid=l+r>>1;

        if( Judge(mid) )

            r=mid;

        else

            l=mid;

    }

    return Judge(l)?l:r;

}

int main()

{

    #ifdef PoPoQQQ

    freopen("stu_tests\\stu4c.in","r",stdin);

    #endif

    int i;

    cin>>n>>m;

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

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

    int ans=Bisection();

    Judge(ans);

    cout<<pos<<' '<<ans<<endl;

    return 0;

}