题解：P14665 [KenOI 2025] 序列题
fish_love_cat · · 题解
要哭出来了，原本以为良心出题人调小数据范围，于是直接开始想
严肃虚空思考 2h 然后没写完。赛后 5min 调出来的已经碎掉了。
想了半天 dp 讨论平台上升下降峰值刷新区间修改，然后心态爆炸了在床上滚了 2h，这一部分对解题毫无帮助的思考全部都扔进垃圾桶了，于是这里略去不提。我不知道 dp 可不可做来着 /kk
注意到这个答案有单调性，于是二分答案。
注意到区间增减有很典的转化是变成差分数组上的单点修改，于是考虑差分。想 dp 的时候完全没发现这个，于是爆炸了 /kk
然后你会发现极差其实就是差分数组的最大子段和或最小子段和。我们把这个叫做绝对值最大子段和。
啊这两个不会求的去主题库里搜「最大子段和」看题解，这里不做解释。
因为只和差分数组有关，于是接下来我们只需要考虑差分数组。
如果当前的这个绝对值最大子段和超出正在检验的答案，那么就要进行调整。
这个调整对于正负两个计数器都会有效果，所以累加答案的同时也要对这两个同时进行修改。
我们把需要进行的增加操作与减去操作分开来存，因为一次操作事实上可以同时完成一个增加和一个减去，于是只需要这二者操作次数的最大值即可。
显然可以把操作点放到序列外面从而把两个操作位置变成零个甚至一个，于是多出来的操作机会可以不管。
于是做完了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[5005];
int b[5005];
int n,m;
bool check(int x){
int mx=0,mn=0;
int ans1=0,ans2=0;
for(int i=2;i<=n;i++){
mx+=b[i];
mn+=b[i];
mx=max(mx,b[i]);
mn=min(mn,b[i]);
if(mx>x)ans1+=mx-x,mn-=mx-x,mx=x;
if(-mn>x)ans2+=-mn-x,mx+=-mn-x,mn=-x;
}
return max(ans1,ans2)<=m;
}
signed main(){
cin>>n>>m;
int mx=-1,mn=1e9;
for(int i=1;i<=n;i++)
cin>>a[i],
mx=max(mx,a[i]),
mn=min(mn,a[i]),
b[i]=a[i]-a[i-1];
int l=0,r=mx-mn;
while(l<r){
int mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<r;
return 0;
}
// 她用指尖轻戳沉睡少女的脸颊。好柔软。
// 手指越压就陷得越深，触感像刚出炉的面包。
// 唔。这有点好玩，而且感觉很舒服。
// 用手指压住，脸颊凹进去。再加一根手指，脸颊歪曲了。
// 爱玛睁开眼睛。
//「…………」
//「…………」