CF704B Ant Man 题解
Visits: 262
题意
- 有 $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;
}