题解：AT_abc395_f [ABC395F] Smooth Occlusion

Laisira · 2025-03-02 13:28:22 · 题解

说句闲话，这题没 B 题难。

显然 H 存在最大值，以及合法情况具有单调性。最大值是 \min_{i=1}^{n}D_i+U_i，考虑二分 H，并维护一个牙齿的可能区间。具体点就是对于每个 U_i 处理出他可能的值，这个值一定是个区间，所以后面的 U_{i+1} 也被确定了一个自己的和关于 U_i 的区间，这两个区间要取并，维护这个区间向后面做判断和转移就行了。

#include<bits/stdc++.h>
using namespace std;
#define bit(x) (x&-x)
#define rep(l,r,i) for(int i=l;i<=r;i++)
#define per(l,r,i) for(int i=l;i>=r;i--)
using namespace std;
#define int long long 
int N;
int X;
vector<int> U, D;
vector<int> sum_UD;
bool is_feasible(int H) {
    int curr_low = max(H - D[0], 0LL);
    int curr_high = min(U[0], H);
    if (curr_low > curr_high) return false;
    rep(1,N-1,i) {
        int a = max(H-D[i], 0LL);
        int b = min(U[i],H);
        int new_low = max(a,curr_low-X);
        int new_high = min(b,curr_high+X);
        if (new_low > new_high) return false;
        curr_low = new_low;
        curr_high = new_high;
    }
    return true;
}
signed main() {
    cin>>N>>X;
    U.resize(N);
    D.resize(N);
    sum_UD.resize(N);
    int H_max = LONG_LONG_MAX;
    rep(0,N-1,i) {
        cin>>U[i]>>D[i];
        sum_UD[i] = U[i] + D[i];
        if (sum_UD[i] < H_max)
            H_max = sum_UD[i];
    }
    int left = 0, right = H_max;
    int best_H = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (is_feasible(mid)) {
            best_H = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    int total_sum = 0;
    for (int s:sum_UD) {
        total_sum += s;
    }
    int cost = total_sum - best_H * N;
    cout<<cost;
    return 0;
}