CF1768D 题解

\(\mathcal Solution\)

【题意】

我们可以交换任意两个数，求最小操作几次能让逆序对变成 \(1\)。

【分析】

如果逆序对为 \(1\) 的排列一定是:

• \(2, 1,\cdots n\)
• \(1, 3, 2,\cdots n\)
• \(1, 2, 4, 3,\cdots n\)
• \(\cdots\)

我们发现这些排列都是由 \(1, 2,\cdots n\) 进行一次交换得来的。

则我们先求出排列 \(p\) 变成 \(1, 2,\cdots n\) 的操作次数。

我们将需要交换的位置连一条边，即 \(\forall i(1\le i\le n)\) 连一条 \(i\to p_i\) 的边。

那么从 \(i\) 出发经过的点为 \(i\to p_i\to p_{p_i}\to\cdots\to i\)。

对于每个环，需要操作的次数即为 \(size-1\)，\(size\) 表示环中的不同点数。

证明：

对于一个环 \(\{i, p_i, p_{p_i},\cdots \}\)，我们记为 \(\{a_1, a_2,\cdots, a_{size}\}\)。

注意：\(a_{size}\neq i\)。

则我们 \(\operatorname{swap}(a_{size}, a_{size-1}), \operatorname{swap}(a_{size-1},a_{size-2}),\cdots,\operatorname{swap}(a_2, a_1)\)，其中 \(\operatorname{swap}(a, b)\) 表示交换 \(a, b\)。这样操作次数是 \(size-1\)。

也就是说答案为 \(n-cnt\)，\(cnt\) 表示环的数量。

那么我们考虑什么时候是能在变成 \(1, 2,\cdots, n\) 之前满足要求。

如果 \(i\) 和 \(i+1\) 是在一个环中，则可以在这之前满足要求。否则，就不能在之前满足要求。

代码。