CF704B Ant Man 题解

作者: xht37 分类: 题解 发布时间: 2020-03-04 18:00

Visits: 262

CF704B Ant Man

题意

  • 有 $n$ 个元素,第 $i$ 个元素有五个参数 $x_i,a_i,b_i,c_i,d_i$。
  • 你需要求出一个 $1 \sim n$ 的排列 $p$,满足 $p_1 = s, p_n = e$,同时最小化这个排列的权值。
  • 一个排列的权值为 $\sum_{i=1}^{n-1} f(p_i, p_{i+1})$,其中 $f(i,j)$ 的值有两种情况:
    • 若 $i > j$,则 $f(i,j) = x_i – x_j + c_i + b_j$。
    • 若 $i < j$,则 $f(i,j) = x_j – x_i + d_i + a_j$。
  • $n \le 5 \times 10^3$,$s \ne e$,$1 \le x_1 < x_2 < \cdots < x_n \le 10^9$,$1 \le a_i,b_i,c_i,d_i \le 10^9$。

题解

考虑贪心,对 $s \to e$ 建立一个链表。

从小到大考虑 $1 \sim n$ 中每个不是 $s,e$ 的元素,枚举它往链表中插入的位置,从最优的位置插入即可。

为什么是对的呢?

注意到,元素的贡献只和左右两个元素的相对大小有关。

先不考虑 $s,e$ 的情况,显然元素是从小到大插入的。

讨论每次插入一个元素时贡献的变化情况,设此时 $x$ 要插入 $y \to z$ 的位置,不妨设 $x > y > z$。

原本的贡献有:

  • $y$ 往小
  • 大往 $z$

插入 $x$ 后的贡献由:

  • $y$ 往大
  • 大往 $z$
  • 小往 $x$
  • $x$ 往小

其中「大往 $z$」的贡献不变,直接消掉;「小往 $x$」和「$x$ 往小」的贡献是固定的,不管从哪儿插入这个贡献都一定存在,因此可以忽略。

即每次会把一个「$y$ 往小」的贡献变成「$y$ 往大」的贡献。

同理,若 $x > z > y$,则每次会把一个「小往 $z$」的贡献变成「大往 $z$」的贡献。

换句话说,对于与「大」相关的贡献,将永远无法被去掉;对于与「小」相关的贡献,在每一次插入操作时,会把原有的一个与「小」相关的贡献变成与「大」相关的贡献,然后加入两个新的与「小」相关的贡献。

这就相当于,有一个集合存储着所有「小」$\to$「大」的贡献,每次在集合中选择一个数去掉,然后加入两个数,要使最后去掉的数之和最小。

显然每次贪心的取最小值即可。

现在要考虑 $s,e$,我们将元素分成 $[1, \min(s,e) – 1],[\min(s,e) + 1, \max(s,e) – 1],[\max(s,e) + 1, n]$ 三个部分分别讨论,可以发现过程和上面的类似。

因此这样贪心是正确的。

由于本题 $n$ 较小,可以直接 $\mathcal O(n^2)$ 解决,但根据上述讨论,我们显然可以优化至 $\mathcal O(n \log n)$。

代码

const int N = 5e3 + 7;
int n, s, e, t[N];
ll x[N], a[N], b[N], c[N], d[N], ans;

inline ll S(int i, int j) {
    return i < j ? x[j] - x[i] + d[i] + a[j] : x[i] - x[j] + c[i] + b[j];
}

int main() {
    rd(n), rd(s), rd(e);
    rda(x, n), rda(a, n), rda(b, n), rda(c, n), rda(d, n);
    ans = S(s, e), t[s] = e;
    for (int i = 1; i <= n; i++)
        if (i != s && i != e) {
            pair<ll, int> o = mp((ll)1e18, 0);
            for (int j = s; j != e; j = t[j])
                o = min(o, mp(S(j, i) + S(i, t[j]) - S(j, t[j]), j));
            t[i] = t[o.se], t[o.se] = i, ans += o.fi;
        }
    print(ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注