题解：AT_abc395_f [ABC395F] Smooth Occlusion

· · 题解

AT_abc395_f [ABC395F] Smooth Occlusion 题解

by cwd2023

思路：

其实本题有多种做法，例如二分，差分约束等，这里介绍一种十分简洁的且只有十行代码的 O(n) 做法。

首先，我们想让磨掉的牙最少，就等于保留尽可能多的牙,所以设 h 表示可保留牙的最大值，设 sum 为所有牙齿的长度和。

先考虑题目中的第二个条件，我们可以设 miu 为上牙可保留的最大值。那么，由于磨牙只能减少长度，所以当新输入的上牙长度小于 miu+x 时，我们就可以更新 miu 使其更小，否则不更新。

那么，为了保证题目中的第一个条件，我们再设 mid 表示下牙可保留的最大值，且 mid 和 miu 必须同步更新，这样保证了它们的和相等。

最后，记得将 h 和 miu 以及 mid 赋上初始值。

代码：

#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;
}

最后，希望本篇题解对你有所帮助，感谢观看。

望管理员通过！