@[qinyubo](/user/172003)
by OrezTsim @ 2022-11-03 18:41:48
我先来，qndmx
上界换成 `a[n]-a[1]`（体现到代码里就是右边界改成 `b[n+1]-b[1]`） 是没问题的，我算出来最大 delta 也是这个玩意吧，为啥是相邻差分啊
by UnyieldingTrilobite @ 2022-11-03 19:45:08
@[UnyieldingTrilobite](/user/250637)
大佬，就是求出 b 数组为 a 数组差分
然后 max_element b（
但是由于是最小值
每一次斜率增加不应该最多为 max_element b 吗
每一次肯定取相邻值更优吧？
by OrezTsim @ 2022-11-03 19:53:22
指相邻的 a 的差值（
by OrezTsim @ 2022-11-03 19:53:55
@[MistZero](/user/487752) 我的感觉是，你考虑一下等于是这样多一条线的流程中间可能会连着改一路，所以不一定是一个点移到相邻吧
胡胡的，有点像网络流退流的那种感觉
by UnyieldingTrilobite @ 2022-11-03 19:57:44
@[UnyieldingTrilobite](/user/250637) 有可能中间把一串给串一起了？
我对于配对个数取的 min
也就是有可能答案相等的情况下我把一段给串起来了
然后这一段 > max_element？
这个意思吗
by OrezTsim @ 2022-11-03 20:01:10
@[MistZero](/user/487752) 是这种感觉吧，就是你不一定就朴素调整一下，可能涉及到别的更改
朴素调整的上界应该是我给的这个
by UnyieldingTrilobite @ 2022-11-03 20:06:19
@[UnyieldingTrilobite](/user/250637) 有道理，谢谢啦
by OrezTsim @ 2022-11-03 20:09:09
求助，我也是wqs二分，用的种树改的，只有80分
by Let_Fly @ 2023-09-06 21:39:08
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
int n,k;
int a[N],val[N];
int maxx=LONG_LONG_MIN;
int xmx,xas,ans=-1;
int dp[N][2],cnt[N][2];
void check(int v){
memset(dp,0,sizeof dp);
memset(cnt,0,sizeof cnt);
dp[1][1]=val[1]-v,cnt[1][1]=1;
for(int i=2;i<=n;i++){
dp[i][1]=dp[i-1][0]+val[i]-v;
dp[i][0]=min(dp[i-1][1],dp[i-1][0]);
cnt[i][1]=cnt[i-1][0]+1;
cnt[i][0]=(dp[i-1][1]<=dp[i-1][0]?cnt[i-1][1]:cnt[i-1][0]);
}
if(dp[n][1]<=dp[n][0]){
xmx=dp[n][1];
xas=cnt[n][1];
}else{
xmx=dp[n][0];
xas=cnt[n][0];
}
}
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
maxx=max(maxx,a[i]);
}
n--;
for(int i=1;i<=n;i++){
val[i]=a[i+1]-a[i];
}
int l=1,r=1e12;
while(l<=r){
int mid=l+r>>1;
check(mid);
// cout<<xmx<<' '<<xas<<' '<<mid<<'\n';
if(xas<=k){
ans=xmx+mid*k;//其实可以最后更新一次就行，但是为了检验二分成功与否，放在这里
l=mid+1;
}else{
r=mid-1;
}
}
if(ans==-1){
check(0);
ans=xmx;
}
cout<<ans;
return 0;
}
```
by Let_Fly @ 2023-09-06 21:39:22