题解：abc395_f F - Smooth Occlusion
xyx404
·
·
题解
翻译：
高桥君有 2 \times N 个牙齿，N 个上排的牙齿和 N 个下排的牙齿。
注：以下为了方便“上牙”指的是上排的牙齿，“下牙”指的是下排的牙齿。
第 i 个上牙的长度为 U_i，第 i 个下牙的长度为 D_i。
有个操作，需要花费一元，选择一个长度大于 0 的牙齿，将其长度减少 1。
求使牙齿“咬合良好”的最小总费用。
牙齿“咬合良好”需要满足以下两个条件：
- 存在一个整数 H，使得对于所有 1 \le i \le N，满足 U_i + D_i 等于 H。
- 对于所有 1 \le i < N，满足 \left |U_i - U_{i+1} \right | \le X。
思路：
二分搜索。
二分寻找符合条件的最大的 H。
找到后计算最小费用就行了，设总费用为 ans，则
ans=\sum_{i=1}^{N}(U_i+D_i-H)
二分查找部分：
为什么可以二分 H 和二分范围：
我们可以发现如果某一个 H 是可行的，因为我们可以使用操作去减少牙齿的长度，所以所有比 H 小的值也可能是可行的，所以我们可以发现 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)$。
先判断第一个上牙的范围是否合法，也就是左端点需要小于等于右端点，因为不可能会出现最大值小于最小值。
接着循环除了第一个牙齿外的其它牙齿，检查相邻上牙的差值是否满足条件。
如果所有上牙都满足条件，返回真，否则返回假。
## 代码：
```cpp
#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;
}
```