CF1672F1 Array Shuffling
chzhc
·
·
题解
题意
给出长度为 n 的数组 a，你需要构造一个 a 的置换 b，使得 b 经过只交换操作后成为 a 的最少交换次数最大。
数据范围：2 \leq n \leq 2 \times 10^5，1 \leq a_i \leq n。
做法
设 a 数组中，元素 i 出现了 cnt_i 次，我们令 cnt_1 \geq cnt_2 \geq \cdots \geq cnt_k（即将元素重编号，按照出现次数排名）。
假设 b 数组已经确定，我们考虑如何求出这个最少交换次数。考虑两个图：
$G_2$：对于某一种方案，若 $b_i$ 最终要移动到位置 $j$ 则连一条 $i \to j$ 的边，容易发现每个点只会有一条出边和一条入边，那么最终的图一定由若干个环组成。
结论 1. 对于某一张图 $G_2$，该方案的最少交换次数 $F(G_2)$ 是 $\operatorname{size}(G_2) - \operatorname{ring}(G_2)$（其中 $\operatorname{size}(G)$ 是图 $G$ 的大小，$\operatorname {ring}(G)$ 表示图 $G$ 环的个数）。
引理 1. 对于 $\operatorname {size}(G) \geq 2$ 的环 $G$，对任意两个不同结点进行交换后会成为两个环。
证明如下：
对于环 $g_1 \to g_2 \to \cdots \to g_k\to g_1$，考虑交换 $g_i, g_j(1 \leq i < j \leq k)$，图会变为 $g_1 \to \cdots \to g_i \to g_{j+ 1} \to \cdots \to g_k \to g_1$ 和 $g_{i + 1} \to \cdots \to g_j \to g_{i + 1}$ 这两个环。
引理 2. 对于两个环，在两个环中各取一个结点进行交换后会合并为一个环。
证明如下：
对于环 $g_1 \to g_2 \to \cdots \to g_k \to g_1$ 和 $f_1 \to f_2 \to \cdots \to f_h \to f_1$，考虑交换 $g_i, f_j(1 \leq i \leq k, 1 \leq j \leq h)$，图会变为 $g_1 \to \cdots \to g_i \to f_{j + 1} \to \cdots \to f_h \to f_1 \to \cdots \to f_j \to g_{i + 1} \to \cdots \to g_k \to g_1$ 这一个环。
引理 3. 对于一个环 $G$，它的最少交换次数 $F(G)$ 为 $\operatorname{size}(G) - 1$。
证明如下：
考虑使用数学归纳法证明：
1. $\operatorname{size}(G) = 1$ 时，$F(G) = 0$，$\operatorname{size}(G) = 2$ 时，$F(G) = 1$；
2. 假设当 $\operatorname{size}(G) \leq k, k \geq 2$ 时，引理 3 成立，当 $\operatorname{size}(G) = k + 1$ 时，肯定是交换两个不同结点，根据引理 1 可知，会分裂出两个环，每个环的大小一定 $\leq k$，即分裂出的两个环都满足引理 3，那么就有 $F(G) = F(G_1) + F(G_2) + 1 = \operatorname{size}(G_1) - 1 + \operatorname{size}(G_2) - 1 + 1 = \operatorname{size}(G) - 1$。即 当 $\operatorname{size}(G) = k + 1$ 时，$F(G) = \operatorname{size}(G) - 1$ 也成立。故引理 3 得证。
结论 1 证明如下：
若每次操作仅对一个环内的结点进行操作，那么根据引理 3 可知，至少要进行 $\operatorname{size}(G) - \operatorname{ring}(G)$ 次，若对不同环的结点进行操作，根据引理 2 可知环会合并，容易发现这样操作一定更劣。
结论 2. 最终方案的图中不会出现一个环内出现两个值相同的元素的情况。
证明如下：
考虑出现两个相同值元素的环：$g_1 \to g_2 \to \cdots \to g_s \to \cdots \to g_t \to \cdots \to g_k \to g_1$（其中 $\operatorname{val}(g_s) = \operatorname{val}(g_t)$），那么根据结论 1，我们会最大化环的个数从而使得交换次数最少，那么上述的环可以分为两个环：$g_1 \to \cdots \to g_s \to g_{t + 1} \to \cdots \to g_k \to g_1$ 和 $g_{s + 1} \to \cdots \to g_t \to g_{s + 1}$，故不可能出现一个环内出现两个值相同的元素的情况。
回到本题，根据结论 1 容易发现我们需要最小化**最大化环**的个数。设 $cnt$ 为 $a$ 中出现次数最多的数的个数。那么根据结论 2，这个环的个数至少有 $cnt$ 个，即最少交换次数最多为 $n - cnt$，下面给出一种构造方案使得答案为 $n - cnt$。
构造如下：
1. 尽可能多地选定各不相同的几个数；
2. 将它们按照 **大小顺序** 循环移动，每个数移动到恰好大于它的那个位置（最大的数移动到 $1$ )。
如：
$$
a = (1, 3, 2, 4, 2, 1, 4)
$$
$$
b = (*, *, *, *, *, *, *)
$$
$$
a = (\mathbf1, \mathbf3, \mathbf2, \mathbf4, 2, 1, 4)
$$
$$
b = (4, 2, 1, 3, *, *, *)
$$
$$
a = (1, 3, 2, 4, \mathbf2, \mathbf1, \mathbf4)
$$
$$
b = (4, 2, 1, 3, 1, 4, 2)
$$
结论 3. 按照上述构造的 $b$，对应的图 $G_1$ 中不存在环不经过出现次数最多的元素 $1$。
证明如下：
若存在这么一个环，我们考虑这个环 $g_1 \to g_2 \to \cdots \to g_k \to g_1$，因为不经过 $1$，所以满足如下式子：
$$
b_{g_1} = a_{g_2} > b_{g_2} = a_{g_3} > \cdots > b_{g_k} = a_{g_1} > b_{g_1}
$$
显然矛盾，故结论 3 得证。
考虑如何方便的构造出上述的 $b$，我们将 $a$ 进行排序，然后按照 $cnt$ 进行循环分组（$a_1$ 放到 $a_{1 + cnt}$ 下，$a_2$ 放到 $a_{2 + cnt}$ 下 ... $a_{n - cnt + 1} \sim a_n$ 均放到 $a_1$ 下），这样便能构造出 $cnt$ 个环，且满足上述条件。
时间复杂度：$\mathcal O(n \log n)$。
[评测链接](https://codeforces.com/contest/1672/submission/155039032)。