题解：P11598 [NOISG 2018 Finals] Safety

· · 题解

思路

设 f_i(x) 表示前 i 个柱子，第 i 个柱子高度为 x 的最小代价，则：

f_i(x) = \min_{j = x - H}^{x + H} f_{i - 1}(j) + |x - h_i|

答案就是 \min_{x}f_n(x)。

显然，f_1(x) 是下凸的，那么对 f_{i - 1}(j) 取 \min 显然是下凸的，|x - h_i| 显然也是下凸的，两个下凸的函数加起来保持凸性，那么 f_i(x) 也是下凸的。

我们考虑使用 slope trick 优化。

对于一个分段下凸函数 f(x)，可以用拐点（斜率变化点）描述。若函数最小值区间为 [L, R]，则：

那么对于本题，我们维护两个拐点集合 A, B，所有负斜率拐点存入 A，正斜率拐点为 B。

那么对于取 \min 操作，就是将函数整体向下“平移”一个斜率 H 的窗口。

对拐点的影响就是负斜率拐点向右移动 H，正斜率拐点向左移动 H。

对于绝对值操作，就是在 x = h_i 处增加一个绝对值一样的 "V" 型尖峰。

对拐点的影响就是往 A 插入一个拐点 h_i，往 B 插入一个拐点 h_i。

考虑使用一个大根堆维护 A，小根堆维护 B，那么 [\max\{A\}, \min\{B\}] 就是最小值区间。

但是我们不便每次操作 A, B 中所有元素，于是我们维护一个整体偏移量 \Delta，对于 A 集合实际拐点值就是 A_x - \Delta，对于 B 集合实际拐点值就是 B_x + \Delta。对于取 \min 操作，增加 \Delta 即可。

设 x 为当前 A 中最大值，y 为当前 B 中最小值。如果 x\le y，[x, y] 就是最小值区间；如果 x > y，说明原本属于 A 的拐点 x 应该属于 B，属于 B 的拐点 y 应该属于 A，于是交换 x, y，插入应该插入的集合，那么函数的最小值被迫上升 |x - y|。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 3e5 + 10;
int n, H, h[MAXN];
int ans, lzy;
priority_queue <int> a;
priority_queue <int, vector <int>, greater <int> > b; 
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> H;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        lzy += H;
        a.push(h[i] + lzy);
        b.push(h[i] - lzy);
        int x = a.top() - lzy, y = b.top() + lzy;
        while (x > y) {
            a.pop(), b.pop();
            ans += abs(x - y);
            a.push(y + lzy);
            b.push(x - lzy);
            x = a.top() - lzy, y = b.top() + lzy;
        }
    }
    cout << ans << '\n';
    return 0;
}