CF704B Ant Man 题解

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