中文题意

现在你一共有个花坛,每个花坛有一定量的起始泥土,现在你要把每个花坛泥土数量变成

你有三种操作分别是:

  1. 花费直接给这个花坛填入一单位泥土,
  2. 花费直接给这个花坛移除一单位泥土,
  3. 如果你想把第个花坛的泥土移动到第个花坛,那么花费就是

现在询问你使得全部花坛数量都变成指定的的最小花费是多少。

Solution

首先我们要做的一个特别点的离散化处理,假设我们把输入的写成

同理把数组也转换出来之后,我们会发现对于每个他们之间就记录了点之间的距离。

如果我们用记录处理了前相同需要最小的花费。

那么边界就是

后续递推方程

但是这样计算复杂度的时候就会发现,这东西复杂度是,过不去这题,但是可以过掉一个简化版本

我们转移的速度太慢了,所以我们需要换一种方式,或者优化掉一维,我们依旧这样离散每一个,但是我们并不去离散,我们在这样的前提下去判断的关系,那么显然如果两者相等直接略过。

如果说明我们要把这个位置的土弄出去,并且还不是仅仅移除一次,我们使用代表处理离散之后的位置需要的最小花费。我们初始化这个值等于移除泥土的花费,我们还有第二种选择,往前面挑一个要泥土的位置放进去,花费就是,因为我们是顺序处理所以我们会先认为位置少了泥土先填了土进去,现在我们从后面移植进去就要减掉之前预先设计的花费。所以我们知道

同理如果说明我们要找到

下面我们考虑如何优化,我们把求最小值拓展开

我们很明显看到对于在同一个花坛中的来说是一个定值,那么要让尽可能小,就要保证尽可能大,那么如何找到之前出现的可以填入泥土的位置,放入大根堆中即可找到最值。

那么还有两个问题,为什么我们要让当前的最小,如果保证了当前最小可以保证和最小吗?还有为什么不把这个找到的留给后面的

对于上述两个问题,先解答第二个问题,对于我们可以找到的来说,一定是最靠近的最优,越往后面靠你会发现是不变的,但是却在变大,那么它就更有可能被选择,对于当前更小的距离来说,还有可能找到更优解。

对于第一个问题,我们实现的过程是一个试探的过程,对于我们找到的每个都只是一个阶段性的结果,我们会把当前阶段的做保留,放在大根堆中,对于下次取出这个位置,就会进行操作,这样根据一个带后悔的贪心进行调整,得到最终的最优解,至此完结撒花。

时间复杂度

#include <bits/stdc++.h>
using namespace std;
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }

const int N = 1e5 + 7;
ll n, x, y, z;

// q1记录多了土的  q2记录少了土的
priority_queue<ll> q1, q2;
ll p[N];

void solve() {
    n = read(), x = read(), y = read(), z = read();
    int a, b;
    ll ans = 0;
    rep(i, 1, n) {
        a = read(), b = read();
        if (a == b)    continue;
        else if (a > b) { // 需要移掉一些土
            rep(j, 1, a - b) {
                p[i] = y; // 首先假设只能花y移走
                if (q2.size()) {
                    p[i] = min(p[i], i * z - q2.top()); // 从少了土的地方,找负的最多的那个过来尝试更新
                    q2.pop();
                }
                ans += p[i]; // 对于每个多了土的地方一定是找到一个 少了土的地方就填进去,往后继续考虑一定不优
                q1.push(p[i] + i * z); // 放进去多了土的地方,给下面更新
            }
        }
        else if (a < b) {
            rep(j, 1, b - a) {
                p[i] = x; //假设只能花x买来
                if (q1.size()) {
                    p[i] = min(p[i], i * z - q1.top()); // 从之前多了土的地方拿来更新
                    q1.pop();
                }
                ans += p[i];
                q2.push(p[i] + i * z);
            }
        }
    }
    print(ans);
}

int main() {
    solve();
    return 0;
}