题解：AT_abc395_f [ABC395F] Smooth Occlusion

首先无论你如何据牙齿，最后的答案都是

(\sum_{i-1}^n U_i+D_i)-nH

。

所以说我们只需要找到一最大的

H

满足据牙齿的条件。

显然对于一个

H

可以锯掉那么所有

H'<H

都可以锯掉。那么我们可以根据该性质二分，找到最大的一个

H

。

那现在只需要考虑为

H

的情况下，是否可以锯掉牙齿。同时，条件仅要求了上牙的情况，那么我们可以指考虑上牙。

那么既然知道

H

。不难发现，第

1

颗上牙的可锯成

[l_1,r_1]=[\max(0,h-D_1),\min(h,U_1)]

；第

i,2\le i

颗上牙可以锯成

[l_i,r_i]=[\max(0,h-D_i),\min(h,U_i)]\land[l_{i-1}-x,r_{i-1}+x]

。

而如果任何一颗上牙的取值为空集，那么则无法锯掉，否则可以。

即可完成此题。

CPP

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, x;
ll u[200001], d[200001];
bool check(ll h) {
	ll l =0, r =3000000000;
	for (int i = 1; i <= n; i++) {
		l = max(max(h - d[i], 0ll), l - x);
		r = min(min(u[i], h), r + x);//计算取值范围
		if(l>r)
			return 0;//判定是否可行
	}
	return 1;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin>>n>>x;
	ll sum=0;
	for(int i=1;i<=n;i++)
		cin>>u[i]>>d[i],sum+=u[i]+d[i];//计算总长度
	ll l=0,r=3000000000;
	while(l<r) {
		ll mid=(l+r)/2;
		if(check(mid+1)) l=mid+1;
		else r=mid;
	}//二分
	cout<<sum-n*l;//输出答案
}

题解：AT_abc395_f [ABC395F] Smooth Occlusion

文章操作

相关推荐

评论

题解：AT_abc395_f [ABC395F] Smooth Occlusion