专栏文章

题解：AT_abc395_f [ABC395F] Smooth Occlusion

ccwd2023
AT_abc395_f题解参与者 15已保存评论 22

文章操作

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

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

AT_abc395_f [ABC395F] Smooth Occlusion 题解

by cwd2023

思路：

其实本题有多种做法，例如二分，差分约束等，这里介绍一种十分简洁的且只有十行代码的 O(n)O(n) 做法。
首先，我们想让磨掉的牙最少，就等于保留尽可能多的牙,所以设 hh 表示可保留牙的最大值，设 sumsum 为所有牙齿的长度和。
先考虑题目中的第二个条件，我们可以设 miumiu 为上牙可保留的最大值。那么，由于磨牙只能减少长度，所以当新输入的上牙长度小于 miu+xmiu+x 时，我们就可以更新 miumiu 使其更小，否则不更新。
那么，为了保证题目中的第一个条件，我们再设 midmid 表示下牙可保留的最大值，且 midmid 和 miumiu 必须同步更新，这样保证了它们的和相等。
最后，记得将 hh 和 miumiu 以及 midmid 赋上初始值。

代码：

CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,u,d,sum,h=2e18,miu=1e18,mid=1e18,x;
int main() {
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>x;
	for(ll i=1;i<=n;i++){
		cin>>u>>d;
		sum+=(u+d);
		miu=min(miu+x,u);
		mid=min(mid+x,d);
		h=min(h,miu+mid);
	}
	cout<<sum-n*h<<"\n";
	return 0;
}
最后，希望本篇题解对你有所帮助，感谢观看。
望管理员通过！

评论

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

正在加载评论...