今日学习记录
1. P14665 [KenOI 2025] 序列题 - 洛谷
关键词：二分答案
问题分析：
给出一个序列,可对其进行区间上的加减一操作,求在进行 m 次操作之后序列的最大值和最小值的极差,要使极差最小
核心思路:
二分答案
我们并不知道最小的极差具体是多少,但是我们知道极差的范围是 0~(max-min),先考虑枚举极差,这样效率贼低,极差是单调的,所以可以使用二分搜索来进行查找该极差,于是二分答案的第一步就迈出了 接下来就是贪心部分,这里也不好解决,在我们已知极差是多少的前提下,我们也无法判断到底加减到哪里,怎么统计次数 我们知道的极差就是最大值和最小值的差值,我们要知道数组中数据之间的差值,就要使用差分数组 还是考虑山峰模型 原数组: 1,2,3,4,5, 4, 3, 2, 2,3,4,5, 4, 3, 2, 1 差分后: 1,1,1,1,1,-1,-1,-1,0,1,1,1,-1,-1,-1,-1 遍历一遍累加的值就是该区间内的最大值和最小值的差值,那么接下来讨论怎么计数,当计数大于 m 就返回 false 可能有人纠结于怎么对数组进行实际的操作,这样的话根本无法下手,所以当差值大于给定极差时,我们之间记录超出的部分就行,我们分加减两个操作进行讨论,记录最大值(进行减操作)和最小值(进行加操作),这里最小值记录的是数组中减的部分,是负值,定义两个 ans1,ans2;因为一次操作实际上能同时完成一个加和减的操作,所以求这两个的之间的最大值 当最大值大于极差的时候,ans1 加上超出部分,最大值赋值为极差,同时这边减了,最小值也要减(作出了与加相反的操作) 当最小值(绝对值,看的是数大小)大于极差的时候,ans2 加上超出部分,赋值为极差,最大值也加 最后返回 max(ans1,ans2)<=m 就行了
**最终代码：
#include <bits/stdc++.h>
using namespace std;
#define ve vector
using ll = long long;
using ull = unsigned long long;
using sr = string;
using db = double;
const int MOD=998244353;
const ll INF=1e18;
const int DIR[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};
int T;
void solve(){
int n,m;cin>>n>>m;
ve<int> arr(n+1),cur(n+1);
int mx = -1,mn = INT_MAX;
for(int i = 1;i<=n;i++){
cin>>arr[i];
cur[i] = arr[i] - arr[i-1];
mx = max(arr[i],mx);
mn = min(arr[i],mn);
}
auto check = [&](int mid) -> bool {
int nmx = 0,nmn = 0,ans1 = 0,ans2 = 0;
for(int i = 2;i<=n;i++){
nmx = max(cur[i],nmx+cur[i]);
nmn = min(cur[i],nmn+cur[i]);
if(nmx>mid) ans1 += nmx - mid,nmn -= nmx - mid,nmx = mid;
if(-nmn>mid) ans2 += -nmn - mid,nmx += -nmn - mid,nmn = -mid;
}
return max(ans1,ans2)<=m;
};
int l = 0,r = mx - mn;
while(l<r){
int mid = l+(r-l)/2;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout<<r;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
T = 1;
while(T--) solve();
}学到的点： 1.