比较明显地能看出二分来，但是检查函数很难写。对于二分出的一个$mid$，我们要让它满足在$m$次操作内令序列中存在一个为零的位置，同时使得任意相邻的两项之差不超过$mid$
第二项的检查比较好做，我们正反各扫一遍然后把扫到的上一个数对当前数与$mid$之差取最小值，就是满足条件的最小代价
对于第一项的检查，我们发现可以将原数列修改成一段段的等差数列，这样在存在零的情况下是最优的。我们枚举这个变成零的位置，然后找出$h_l-k-l*mid>0$和$h_r-r-k*mid>0$的$l,r$，这两个端点具有单调性，可以用双指针扫描解决
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=1000005; 6 long long h[N],tmp[N],fsum[N],cst[N]; 7 long long n,m,l,r,f,b,ans1,ans2; 8 long long check(long long x) 9 { 10 long long tep=0; 11 for(int i=1;i<=n;i++) tmp[i]=h[i]; 12 for(int i=2;i<=n;i++) 13 if(tmp[i]>tmp[i-1]+x) 14 tep+=tmp[i]-tmp[i-1]-x,tmp[i]=tmp[i-1]+x; 15 for(int i=n-1;i;i--) 16 if(tmp[i]>tmp[i+1]+x) 17 tep+=tmp[i]-tmp[i+1]-x,tmp[i]=tmp[i+1]+x; 18 if(m<tep) return 0; 19 for(int i=1;i<=n;i++) fsum[i]=fsum[i-1]+tmp[i]; 20 memset(cst,0,sizeof cst); f=1,b=n; 21 for(int i=0;i<n;i++) 22 { 23 while(f<=i&&tmp[f]<=1ll*(i-f+1)*x) f++; 24 cst[i+1]+=fsum[i]-fsum[f-1]-1ll*(i-f+1)*(i-f+2)*x/2; 25 } 26 for(int i=n+1;i>=2;i--) 27 { 28 while(b>=i&&tmp[b]<=1ll*(b-i+1)*x) b--; 29 cst[i-1]+=fsum[b]-fsum[i-1]-1ll*(b-i+1)*(b-i+2)*x/2; 30 } 31 for(int i=1;i<=n;i++) 32 if(tep+cst[i]+tmp[i]<=m) return i; 33 return 0; 34 } 35 int main () 36 { 37 scanf("%lld%lld",&n,&m); 38 for(int i=1;i<=n;i++) 39 scanf("%lld",&h[i]),r=max(r,h[i]); 40 while(l<=r) 41 { 42 long long mid=(l+r)/2; 43 if(check(mid)) r=mid-1,ans2=mid; else l=mid+1; 44 } 45 ans1=check(ans2); 46 printf("%lld %lld",ans1,ans2); 47 return 0; 48 }