给定一个非负整数序列A，每次操作可以选择一个数然后减掉1，要求进行不超过m次操作使得存在一个Ak=0且max{|Ai−Ai+1|}最小，输出这个最小lk以及最小值。
Solution
最大值最小，显然是需要二分的，而且我们发现答案确实是有单调性的。
接下来我们正着扫一遍整个序列，把差值大于二分出来的值的数调整值合法。
接下来我们就要考虑ak=0的情况，这个东西并没有什么单调性，我们只能从头枚举，直到找到第一个满足要求的就可以了。
考虑当一个数变成零之后，为了满足我们二分出来的答案，我们需要构造这样一个东西。
0 0
0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
两边是等差数列，为了计算序列的长度，我们需要计算出两个数组表示当ai=0是等差数列的左端点和右端点。
我们可以把左右分开算。
比如计算右端点，我们从i向右暴力扩展，当发现当前数字的值小于目标值是就不再扩展了，因为后面已经符合要求了。
最后枚举点，用等差数列求和算一下就可以了。
Code
#include<iostream>
#include<cstdio>
#define N 1000002
using namespace std;
typedef long long ll;
ll ans2,ans,b[N],s1[N],le[N],ri[N],a[N],n,m,sum[N];
bool check(ll pos){
ll num=;
for(int i=;i<=n;++i)b[i]=a[i];
for(int i=;i<=n;++i)
if(b[i]-b[i-]>pos)num+=b[i]-b[i-]-pos,b[i]=b[i-]+pos;
if(num>m)return ;
for(int i=n-;i>=;--i)
if(b[i]-b[i+]>pos)num+=b[i]-b[i+]-pos,b[i]=b[i+]+pos;
if(num>m)return ;
for(int i=;i<=n;++i)sum[i]=sum[i-]+b[i];
for(int i=,j=;i<=n;++i){
while(b[j]<=(i-j)*pos&&j<i)j++;
le[i]=j;
}
for(int i=n,j=n;i>=;--i){
while(b[j]<=(j-i)*pos&&j>i)j--;
ri[i]=j;
}
for(int i=;i<=n;++i)
if((num+sum[ri[i]]-sum[le[i]-]-pos*((i-le[i])*(i-le[i]+)+(ri[i]-i)*(ri[i]-i+))/)<=m)
{ans=i;return ;}
return ;
}
int main(){
scanf("%lld%lld",&n,&m);
ll l=,r=1e9;
for(int i=;i<=n;++i)scanf("%lld",&a[i]);
while(l<=r){
int mid=(l+r)>>;
if(check(mid)){
ans2=mid;
r=mid-;
}
else l=mid+;
}
printf("%lld %lld",ans,ans2);
return ;
}