题意翻译
给定一个非负整数序列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<bits/stdc++.h> 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 k bool 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<n&&b[R]>=(R-i)*mid) sum+=b[R],R++; while(L<i&&b[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; }