2021-03-24 16:35 已编辑牛客运营

关注

【每日一题】2021年3月24日题目精讲

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

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

题解

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

中文题意

现在你一共有 $n\le10^5$ 个花坛，每个花坛有一定量的起始 $a_i$ 泥土，现在你要把每个花坛泥土数量变成 $b_i$ 。 $a_i,b_i\le10$

你有三种操作分别是：

花费 $X$ 直接给这个花坛填入一单位泥土， $X\le10^8$
花费 $Y$ 直接给这个花坛移除一单位泥土， $Y\le10^8$
如果你想把第 $i$ 个花坛的泥土移动到第 $j$ 个花坛，那么花费就是 $Z*|i-j|$ ， $Z\le10^3$

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

Solution

首先我们要做的一个特别点的离散化处理，假设我们把输入的 $a=1,3,2,1$ 写成 $A=1,2,2,2,3,3,4$ 。

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

如果我们用 $f[i,j]$ 记录处理了前 $A[i]$ 和 $B[j]$ 相同需要最小的花费。

那么边界就是 $f[0,j]=j*X,f[i,0]=i*Y$

后续递推方程 $f[i][j]=\min(f[i-1,j]+X,f[i,j-1]+Y,f[i-1,j-1]+Z*|A_i-B_j|)$

但是这样计算复杂度的时候就会发现，这东西复杂度是 $O(100n^2)$ ，过不去这题，但是可以过掉一个简化版本。

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

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

同理如果 $a_i<b_i$ 说明我们要找到 $p_i=\min(X,Z*(i-j)-p_j)$

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

$p_i=\min(Y,Z*(i-j)-p_j)\ \ (j<i)\\p_i=\min(Y,i*Z-(j*Z+p_j))$

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

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

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

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

时间复杂度 $O(10n\log(10n))$ 。

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

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