二分答案mid，将差距先都调到mid以内。

首先从左往右扫，a[i]=min(a[i],a[i-1]+mid)。

然后从右往左扫，a[i]=min(a[i],a[i+1]+mid)。

枚举要变为0的位置，求出L,R使得：

a[L]>(i-L)mid

a[R]>(R-i)mid

此时只需要把[L,i]和[i,R]修改成一个等差数列即可满足条件且代价最小。

注意到随着i的右移，L递增；随着i的左移，R递减，所以可以$O(n)$完成判定。

 

#include
     
      #define N 1000010typedef long long ll;int n,i,j,a[N],b[N],l,r,t,mid,z,k;ll m,s[N],f[N],now;inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline int min(int a,int b){return a
      
       m)return 0;  }  for(i=j=1;i<=n;i++){    while(j
       
        <=(ll)(i-j)*mid)j++;    f[i]=s[i-1]-s[j-1]-(ll)(1+i-j)*(i-j)*mid/2;  }  for(i=j=n;i;i--){    while(j>i&&b[j]<=(ll)(j-i)*mid)j--;    f[i]+=s[j]-s[i]-(ll)(1+j-i)*(j-i)*mid/2;  }  for(i=1;i<=n;i++)if(f[i]+b[i]+now<=m)return i;  return 0;}int main(){  read(n),scanf("%lld",&m);  for(i=1;i<=n;i++)read(a[i]),r=r>a[i]?r:a[i];  while(l<=r)if(t=check(mid=(l+r)>>1))r=(z=mid)-1,k=t;else l=mid+1;  return printf("%d %d",k,z),0;}