D. Lucky Permutation
You are given a permutation$^\dagger$ $p$ of length $n$.
In one operation, you can choose two indices $1 \le i < j \le n$ and swap $p_i$ with $p_j$.
Find the minimum number of operations needed to have exactly one inversion$^\ddagger$ in the permutation.
$^\dagger$ A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
$^\ddagger$ The number of inversions of a permutation $p$ is the number of pairs of indices $(i, j)$ such that $1 \le i < j \le n$ and $p_i > p_j$.
Input
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$).
The second line of each test case contains $n$ integers $p_1,p_2,\ldots, p_n$ ($1 \le p_i \le n$). It is guaranteed that $p$ is a permutation.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
Output
For each test case output a single integer — the minimum number of operations needed to have exactly one inversion in the permutation. It can be proven that an answer always exists.
Example
input
4 2 2 1 2 1 2 4 3 4 1 2 4 2 4 3 1
output
0 1 3 1
Note
In the first test case, the permutation already satisfies the condition.
In the second test case, you can perform the operation with $(i,j)=(1,2)$, after that the permutation will be $[2,1]$ which has exactly one inversion.
In the third test case, it is not possible to satisfy the condition with less than $3$ operations. However, if we perform $3$ operations with $(i,j)$ being $(1,3)$,$(2,4)$, and $(3,4)$ in that order, the final permutation will be $[1, 2, 4, 3]$ which has exactly one inversion.
In the fourth test case, you can perform the operation with $(i,j)=(2,4)$, after that the permutation will be $[2,1,3,4]$ which has exactly one inversion.
解题思路
首先由于最终的排列必须恰好存在一个逆序对，因此最终的排列就有下面这$n-1$种可能。
- ${\color{red}{2}}, {\color{red}{1}}, 3, 4, \ldots, n - 1, n$
- $1, {\color{red}{3}}, {\color{red}{2}}, 4, \ldots, n - 1, n$
- $1, 2, {\color{red}{4}}, {\color{red}{3}}, \ldots, n - 1, n$
...
- $1, 2, 3, 4, \ldots, {\color{red}{n}}, {\color{red}{n - 1}}$
现在就是通过交换序列中的两个元素，使得通过最小的交换次数将原序列变成这$n-1$个序列中的其中一个。
由于是交换任意两个元素且求最小交换次数，因此容易联想到置换群。
这里简单说一下置换群，对于原序列$p$，对每一个下标$i$连一条有向边$i \rightarrow p_i$，那么就会建立一个由若干个环构成的图，这就叫做置换群。如果交换的两个元素在同一个环中，那么这个环就会裂开成两个环。如果交换的两个元素不在同一个环中，那么这两个环就和合并成一个环。可以通过并查集来求得原序列有多少个环（也就是求有多少个连通块）。
很明显，一个长度为$n$的升序排列就构成了$n$个环，假设一开始原序列有$\text{cnt}$个环，由于要将原序列变成升序的排列，因此需要将$\text{cnt}$个环裂成$n$个环，由于每次交换最多可以将一个环裂开成两个，因此至少需要交换$n - \text{cnt}$次。
因此一种方案是先将原序列变成升序的排列，然后再交换任意两个相邻的元素一次，就得到满足题目要求的排列，交换次数是$n - \text{cnt} + 1$，但这不一定是最优解。
其实可以发现最终的序列有$n-1$个环，并且其中一个环的大小为$2$，环中的两个元素相差恰好为$1$。因此如果原序列的某个环本来就存在两个差值为$1$的元素，那么就直接把这两个元素保留在环中，那么最后最小的交换次数就是$n - \text{cnt} - 1$。而如果原序列的每个环都不存在两个差值为$1$的元素，那么在变成升序序列后还要交换两个相邻元素，答案就是$n - \text{cnt} + 1$。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 typedef long long LL;
5
6 const int N = 2e5 + 10;
7
8 int a[N];
9 int fa[N];
10
11 int find(int x) {
12 return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
13 }
14
15 void solve() {
16 int n;
17 scanf("%d", &n);
18 for (int i = 1; i <= n; i++) {
19 scanf("%d", a + i);
20 fa[i] = i;
21 }
22 int cnt = n; // 一开始有n个环
23 for (int i = 1; i <= n; i++) {
24 int x = find(i), y = find(a[i]); // i -> a[i]
25 if (x != y) {
26 fa[x] = y;
27 cnt--; // 合并，环少了一个
28 }
29 }
30 for (int i = 1; i < n; i++) {
31 if (find(i) == find(i + 1)) { // 两个相邻的元素在同一个环中
32 printf("%d\n", n - cnt - 1);
33 return;
34 }
35 }
36 printf("%d\n", n - cnt + 1);
37 }
38
39 int main() {
40 int t;
41 scanf("%d", &t);
42 while (t--) {
43 solve();
44 }
45
46 return 0;
47 }
参考资料
Codeforces Round #842 (Div. 2) Editorial：https://codeforces.com/blog/entry/110901
Codeforces Round #842 (Div. 2) D(置换环)：https://zhuanlan.zhihu.com/p/596949353
标签：cnt,le,int,Permutation,Lucky,序列,permutation,test From： https://www.cnblogs.com/onlyblues/p/17106752.html