题意翻译

给定一个非负整数序列A，每次操作可以选择一个数然后减掉1，要求进行不超过m次操作使得存在一个Ak=0且max⁡(∣xi−xi−1∣)最小，输出这个最小值以及此时最小的k

(1≤n≤1 000 000，1≤m≤10^18)

题解：

最大值最小，还要输出，那就直接二分咯。

由于每次都只能减，所以，

每次二分的内部，可以先把max(|xi-xi-1|)调出来。

从左到右扫一遍，a[i]>a[i-1]+mid 那么a[i]=a[i-1]+mid tot+=a[i]-（a[i-1]+mid)

从右到左扫一遍，a[i-1]>a[i]+mid 同理。

注意循环顺序。因为不能先砍最高的。可能之后更低的会更低。

这样最少的次数保证了max(..)<=mid

然后改枚举最低点的k了。

如果不存在一个点为0

那么，这个点为k的话，两边一定是一个倒阶梯。

回文阶梯形状双等差数列

这个阶梯的L，R有单调性。（L即为i左边第一个可以不用删的位置。R为i右边第一个可以不用删的位置。）

可以直接移动。

具体一些，如果L+1位置比所需的小，那么可以右移L，

如果R不行，那么右移R，直到比所需的位置小。其实同理。

 

 

 

注意，正反循环顺序保证正确性。

双指针移动判定条件及边界。

等差数组求和别写错...

 

代码：

#include
     
      using namespace std;typedef long long ll;const int N=1000000+5;int n;ll m;ll a[N],b[N],c[N];ll ans,pos;int lp;//min a[k]'s kbool che(ll mid){    memcpy(b,a,sizeof a);    ll tot=0;    lp=0;    for(int i=n-1;i;i--){        if(b[i]-b[i+1]>mid) tot+=b[i]-(b[i+1]+mid),b[i]=b[i+1]+mid;     }    for(int i=2;i<=n;i++){        if(b[i]-b[i-1]>mid) tot+=b[i]-(b[i-1]+mid),b[i]=b[i-1]+mid;    }    if(tot>m) return false;    ll L=1,R=1;    ll sum=0;    ll len=0,nd=0;    for(int i=1;i<=n;i++){        while(R
      
       =(R-i)*mid) sum+=b[R],R++;        while(L
       
        <=(i-L)*mid) sum-=b[L],L++;        len=R-i-1;        nd=(len+1)*len/2*mid;        len=i-L;        nd+=(len+1)*len/2*mid;        if(sum-nd+tot<=m){            lp=i;return true;        }    }    return false;}int main(){    scanf("%d%lld",&n,&m);    ll l=0,r=0;    for(int i=1;i<=n;i++){        scanf("%lld",&a[i]);        r=max(r,a[i]);    }    while(l<=r){        ll mid=(l+r)>>1;        if(che(mid)) ans=mid,pos=lp,r=mid-1;        else l=mid+1;    }    printf("%lld %lld",pos,ans);    return 0;}