专栏文章

题解：AT_abc395_f [ABC395F] Smooth Occlusion

LLovely_yhb
AT_abc395_f题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq3ek2b
此快照首次捕获于
2025/12/03 22:18
3 个月前
此快照最后确认于
2025/12/03 22:18
3 个月前
查看原文

题意

有两个长度为 nn 的序列 uiu_i 和 did_i，每次操作可以把一个正数减一，问最少经过次操作使得：
  1. 存在 HH 使所有 ui+di=Hu_i+d_i=H。
  2. 序列中相邻两个数的差小于等于 xx。

思路

这道题可以二分答案去做。
只需要确定 HH，答案就是所有数字的总和减去 H×nH\times n。
二分答案 HH，下界是 00，上界是 min⁡(ui+di)\min(u_i+d_i)。
设 Ui,DiU_i,D_i 分别表示操作完后的 uiu_i 和 did_i。因为 Ui+Di=HU_i+D_i=H，所以只要一个确定了，另一个也确定，那我们就只考虑 UiU_i。
因为每次操作只能减少，所以有 Ui≤ui,Di≤diU_i\le u_i,D_i\le d_i。
对于 Di=H−Ui≤diD_i=H-U_i\le d_i 推出 Ui≥H−diU_i\ge H-d_i。
又因为每个数都要大于等于 00 且小于等于 HH。所以 UiU_i 的范围是区间 [max⁡(0,H−di),min⁡(ui,H)][\max(0,H-d_i),\min(u_i,H)]。
对每个 UiU_i，记录它的取值区间左端点 LL 和右端点 RR。
第 ii 个数的取值区间必须是两个约束的交集：
  1. 自身的区间 [max⁡(0,H−di),min⁡(ui,H)][\max(0,H-d_i),\min(u_i,H)]。
  2. 能够和前一个数的差不超过 xx，即必须落在区间 [Li−1−x,Ri−1+x][L_{i-1}-x,R_{i-1}+x] 内。
因此，对每个 ii，Li=max⁡(0,H−di,Li−1−x),Ri=min⁡(H,ui,Ri−1+x)L_i=\max(0,H-d_i,L_{i-1}-x),R_i=\min(H,u_i,R_{i-1}+x)。
如果对于某个 ii，Li>RiL_i>R_i，说明不合法。check 函数就是这样写的。

AC Code

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,x,u[N],d[N];
bool check(int H) {
	int L=max(0ll,H-d[1]),R=min(u[1],H);
	if(L>R) return 0;
	for(int i=2;i<=n;i++){
		int curL=max(0ll,H-d[i]),curR=min(u[i],H);
		curL=max(curL,L-x),curR=min(curR,R+x);
		if(curL>curR) return 0;
		L=curL,R=curR;
	}
	return 1;
}
signed main() {
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>x;
	int sum=0;
	for(int i=1; i<=n; i++) cin>>u[i]>>d[i];
	for(int i=1; i<=n; i++) sum+=u[i]+d[i];
	int maxn=1145141919810ll;
	for(int i=1; i<=n; i++) maxn=min(maxn,u[i]+d[i]);
	int l=0,r=maxn,anss=0;
	while(l<=r) {
		int mid=(l+r)/2;
		if(check(mid)) anss=mid,l=mid+1;
		else r=mid-1;
	}
	cout<<sum-n*anss;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...