题解 CF704B 【Ant Man】

> [CF704B Ant Man](https://codeforces.com/contest/704/problem/B) ## 题意 - 有 $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)$。 ## 代码 ```cpp 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; } ```