slope trick

EricWan · 2025-04-14 23:05:33 · 题解

怎么没有题解啊（刚才那个人机题解好像被撤下去了），写一篇。

AT 神奇题目之重重壁。

这篇题解应该很详细了。

几个显然的性质：

• 本题只与 a_i-b_i 有关，证明显然
  • 如果当前位置太多了，肯定直接使用去 b_i 个。如果我不这样干，肯定有一个时刻 a_i<b_i，然后会有别的地方运送过来，那就不如让这个最后被送过来的提前被送过来然后送走。
  • 反之，如果当前位置太少了，也是先用去 a_i 个壁不劣。
  • 综上，一开始就送走 \min\{a_i,b_i\} 是正确的
• 相邻两个位置之间不可能同时存在向左运和向右运的壁，证明显然，也是反证，这里不证了

我们先定义 k_i=a_i-b_i，这样后面可以少写一些字，定义 x_i 为从 i 位置运送到 i+1 位置的壁的数量，x_0=x_n=0。

这样题目就转化为了求 (\sum_{i=1}^{n-1}|x_i|)_{\min}，使得 x_{i-1}-x_i\ge k_i。

想到这一步，应该可以列出 DP 转移了。

我们把 x_{i-1}-x_i\ge k_i 移项，得到 x_{i-1}\ge x_i+k_i 换句话说，dp_{i,x_i} 由 \min\{dp_{i-1,x_i+k_i\dots\inf}\} 转移得到，具体转移方程为

初始化为 dp_{0,0}=0,dp_{0,i\neq0}=\inf。

然后这个式子的每一步都恰好是一个 slope trick 可以处理的操作，拿出我们的 slope trick 板子就好啦。

#include <bits/stdc++.h>
using namespace std;
template<typename T>
struct slope_trick { // turning points, min mode
    multiset<T> L, R;
    T minf, L_delta, R_delta;
    slope_trick() : L(), R(), minf(0), L_delta(0), R_delta(0) {}
    bool empty() { return L.empty() && R.empty(); }
    size_t size() { return L.size() + R.size(); }
    T min() { return minf; }
    T L_top() { return *--L.end() + L_delta; }
    T R_top() { return *R.begin() + R_delta; }
    void L_push(T x) { L.insert(x - L_delta); }
    void R_push(T x) { R.insert(x - R_delta); }
    T L_pop() {
        T ans = *--L.end() + L_delta;
        L.erase(--L.end());
        return ans;
    }
    T R_pop() {
        T ans = *R.begin() + R_delta;
        R.erase(R.begin());
        return ans;
    }
    void prefix_min() {
        R.clear();
        R_delta = 0;
    }
    void suffix_min() {
        L.clear();
        L_delta = 0;
    }
    void add_1(T a) { // add (x-a)+
        if (!L.empty()) minf += max(T(0), L_top() - a);
        L_push(a);
        R_push(L_pop());
    }
    void add_2(T a) { // add (a-x)+
        if (!R.empty()) minf += max(T(0), a - R_top());
        R_push(a);
        L_push(R_pop());
    }
    void add_abs(T a) { // add |x-a|
        add_1(a);
        add_2(a);
    }
    void slide_window(T l, T r) {
        L_delta -= r;
        R_delta -= l;
    }
    T operator[](T x) { // some untested
        if (R.empty() && x >= L_top()) return min();
        if (L.empty() && x <= R_top()) return min();
        if (x >= L_top() && x <= R_top()) return min();
        if (!L.empty() && x < L_top()) { // untested
            x -= L_delta;
            T ans = minf, k = 0;
            for (typename multiset<T>::iterator it = --L.end(); ; it--) {
                if (it == L.begin()) {
                    ans += (*it - x) * ++k;
                    break;
                }
                typename multiset<T>::iterator nxt = it;
                nxt--;
                if (x >= *nxt) {
                    ans += (*it - x) * ++k;
                    break;
                }
                ans += (*it - *nxt) * ++k;
            }
            return ans;
        } else {
            x -= R_delta;
            T ans = minf, k = 0;
            for (typename multiset<T>::iterator it = R.begin(); ; it++)
            {
                typename multiset<T>::iterator nxt = it;
                nxt++;
                if (it == --R.end() || x <= *nxt)
                {
                    ans += (x - *it) * ++k;
                    break;
                }
                ans += (*nxt - *it) * ++k;
            }
            return ans;
        }
    }
};
template<typename T>
ostream &operator<<(ostream &a, slope_trick<T> b) {
    a << "<slope trick: min = " << b.minf << ", L = {";
    for (typename multiset<T>::iterator it = b.L.begin(); it != b.L.end();) {
        a << *it + b.L_delta;
        it++;
        if (it != b.L.end()) {
            a << ",";
        }
    }
    a << "}, R = {";
    for (typename multiset<T>::iterator it = b.R.begin(); it != b.R.end();) {
        a << *it + b.R_delta;
        it++;
        if (it != b.R.end()) {
            a << ",";
        }
    }
    return a << "}>";
}
#define int long long
slope_trick<int> f;
int n, k[10000005], a[10000005], b[10000005];
signed main() {
    cin >> n;
    for (int i = 1; i <= 2 * n; i++) { // 初始化只有 dp[0][0] = 0
        f.add_abs(0);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        k[i] = a[i] - b[i];
    }
    for (int i = 1; i <= n; i++) {
        f.suffix_min(); // 后缀最小值
        f.slide_window(- k[i], - k[i]); // 挪动一下
        f.add_abs(0); // 加入那个 |x_i|
    }
    cout << f[0] << endl; // 结果就是 dp[n][0]
    return 0;
}