题解：AT_abc395_f [ABC395F] Smooth Occlusion

· · 题解

首先注意到，第二个限制和 H 无关，所以我们可以从第二个限制入手。

注意到绝对值比较难搞，所以我们可以从小到大考虑，那么就是 U_v - U_u \le x，其中 v = u - 1 或 v = u + 1。那么这就是差分约束了。当然，其实并不需要真的建图，直接向两边走即可。

而最后的答案很明显取决于 H，即 ans = sumh - n \times H。所以我们只要让 H 最小即可。显而易见，H 的最小值就是差分约束之后最小的和。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 200005
il ll rd(){
    ll s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
ll n = rd(), x = rd(), h1[N], h2[N], dis[N], vis[N], sum, ans = 1e18;
priority_queue <pair<ll, ll> > q; 
int main(){
    for (int i = 1; i <= n; i++) h1[i] = rd(), h2[i] = rd(), sum += h1[i] + h2[i];
    for (int i = 1; i <= n; i++) q.push({-h1[i], i}), vis[i] = 0, dis[i] = h1[i];
    while (q.size()){
        ll u = q.top().second;q.pop();
        if (vis[u]) continue;vis[u] = 1;
        if (u > 1 && dis[u - 1] > dis[u] + x) dis[u - 1] = dis[u] + x, q.push({-dis[u - 1], u - 1});
        if (u < n && dis[u + 1] > dis[u] + x) dis[u + 1] = dis[u] + x, q.push({-dis[u + 1], u + 1}); 
    }for (int i = 1; i <= n; i++) ans = min(ans, dis[i] + h2[i]);
    printf ("%lld\n", sum - n * ans);
    return 0;
}