题解：abc395_f F - Smooth Occlusion

{% link 洛谷文章链接,xyx404,https://www.luogu.com.cn/article/q1jz2m4o %}

翻译：

#

高桥君有 $2 \times N$ 个牙齿，$N$ 个上排的牙齿和 $N$ 个下排的牙齿。

注：以下为了方便“上牙”指的是上排的牙齿，“下牙”指的是下排的牙齿。

第 $i$ 个上牙的长度为 $U_i$，第 $i$ 个下牙的长度为 $D_i$。

有个操作，需要花费一元，选择一个长度大于 $0$ 的牙齿，将其长度减少 $1$。

求使牙齿“咬合良好”的最小总费用。

牙齿“咬合良好”需要满足以下两个条件：

1. 存在一个整数 $H$，使得对于所有 $1 \le i \le N$，满足 $U_i + D_i$ 等于 $H$。
2. 对于所有 $1 \le i < N$，满足 $\left |U_i - U_{i+1} \right | \le X$。

思路：

#

二分搜索。

二分寻找符合条件的最大的 $H$。

找到后计算最小费用就行了，设总费用为 $ans$，则

二分查找部分：

#

为什么可以二分 $H$ 和二分范围：

#

我们可以发现如果某一个 $H$ 是可行的，因为我们可以使用操作去减少牙齿的长度，所以所有比 $H$ 小的值也可能是可行的，所以我们可以发现 $H$ 是满足单调性的。

$H$ 的左边界是 $0$，因为所有牙齿的长度都为 $0$ 时一定是满足条件的；$H$ 的右边界是所有 $U_i+D_i$ 的最小值，因为需要满足 $U_i + D_i$ 等于 $H$，而我们的操作只能减少长度，不能增加长度。

查询是否符合条件：

#

定义两个数组 $a$ 和 $b$，$a_i$ 是第 $i$ 个上牙的最小可能长度，$b_i$ 是第 $i$ 个上牙的最大可能长度。

因为必须满足 $U_i + D_i$ 等于 $H$，所以我们可以得出 $U_i$ 必须满足 $U_i=H-D_i$，由于长度至少要是 $0$，所以 $a_i=\max(0,H-D_i)$。

因为第 $i$ 个上牙的长度只有 $U_i$，而在第 $i$ 个下牙为 $0$ 时，要满足条件长度应该等于 $H$，所以 $b_i=\min(U_i,H)$。

先判断第一个上牙的范围是否合法，也就是左端点需要小于等于右端点，因为不可能会出现最大值小于最小值。

接着循环除了第一个牙齿外的其它牙齿，检查相邻上牙的差值是否满足条件。

如果所有上牙都满足条件，返回真，否则返回假。

代码：

#

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
LL T=1,n,m,x;
LL u[int(2*1e5+10)],d[int(2*1e5+10)];
LL al[int(2*1e5+10)],bl[int(2*1e5+10)];
vector<LL>sum_ud;
bool check(LL mid){
	for(int i=0;i<n;i++){
		al[i]=max(0ll,mid-d[i]);
		bl[i]=min(u[i],mid);
	}
	LL cl=al[0],cr=bl[0];
	if(cl>cr)return 0;
	for(int i=1;i<n;i++){
		LL pl=cl,pr=cr;
		LL nl=max(al[i],pl-x),nr=min(bl[i],pr+x);
		if(nl>nr)return 0;
		cl=nl;
		cr=nr;
	}
	return 1;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	while(T--){
		cin>>n>>x;
		sum_ud.resize(n);
		for(int i=0;i<n;i++){
			cin>>u[i]>>d[i];
			sum_ud[i]=u[i]+d[i];
		}
		LL hm=*min_element(sum_ud.begin(),sum_ud.end());
		int l=0,r=hm,anss=0;
		while(l<=r){
			LL mid=l+(r-l)/2;
			if(check(mid)){
				anss=mid;l=mid+1;
			}
			else r=mid-1;
		}
		LL ans=0;
		for(int i=0;i<n;i++){
			ans+=sum_ud[i]-anss;
		}
		cout<<ans;
	}
	return 0;
}