题解：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]。

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

即可完成此题。

#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;//输出答案
}