题号 NC24444
名称 Landscaping
来源 USACO
每日一题三期汇总贴~


如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：jxnu19-软技1班-刘晟

中文题意

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

你有三种操作分别是：

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;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目3月31日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴