置换环
置换环是用来求解将乱序排列变成有序排列所需最小交换次数这一类的问题。
思想：每个元素都向其下标建一条边，最终每个元素都会在一个环中，这个环就是置换环，可知最优情况下元素之间的交换都只会在一个环内进行，一个环最小的交换次数就为 \(size\)（环中元素数量）\(– 1\)。
例如，对于 \(P = {4, 2, 1, 3}\)，\(P[i]\) 都向 \(i\) 建边，可得置换环：
\(4 \to 1 \to 3 \to 4\) 和 \(2 \to 2\)
对于第一个置换环所需交换次数为 \(3\)，第二个置换环需要为 \(0\) 次。
对于一个长度为 \(n\) 的排列，如果其有 \(C\) 个环，每个环的大小为 \(size_i\)，那么总的交换次数就为：
$$\sum size_i – 1 = n – C$$
在置换环中每次交换会产生的影响，设当前交换的两个元素为 \((i, j)\)：
- 如果 \((i, j)\) 在同一个置换环 \(G\) 中，交换后，如果其中一个元素到达了正确位置，该置换环 \(G\) 会分分裂成两个小的置换环 \(G_1\) 和 \(G_2\)，此时所需交换次数会 \(-1\)，置换环个数会 \(+1\)。
- 如果 \((i, j)\) 不在同一个置换环 \(G\) 中，既在置换环 \(G_1\) 和 \(G_2\) 中，交换后，\(G_1\) 和 \(G_2\) 会合并成一个大的置换环 \(G\)，此时所需交换次数会 \(+1\)，置换环个数会 \(-1\)。
模板
void miyan()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
int cnt = 0;
vector<int> id(n + 1, 0);
vector<int> size(n + 1, 0);
for (int i = 1; i <= n; ++i)
{
if (id[i])
continue;
++cnt;
int cur = i;
while (id[cur] == 0)
{
++size[cnt];
id[cur] = cnt;
cur = a[cur];
}
}
}其中：
- \(a\) 为原始数组；
- \(cnt\) 为最终置换环的数量；
- \(size\) 为每个置换环大小；
- \(id\) 为当前元素所属的置换环编号。
注意：通过置换环的性质可知，其天然可以通过并查集解。
1. Minimum Swap
链接：https://atcoder.jp/contests/abc436/tasks/abc436_e
题目描述：
给定一个非恒等排列 \(P\)，设将其变为升序排列 \((1,2,…,N)\) 所需的最少交换次数为 \(K\)，问有多少种不同的合法第一次交换 \((i,j)\)，使得存在一种后续操作序列，在总共恰好 \(K\) 次交换内完成排序。
思路：
置换环模板题。
容易想到任意一个置换环中的任意一对 \((i, j)\) 都可以作为答案，因此对于一个置换环其对答案贡献为 \(C_{size}^{2}\)，其中 \(size\) 为置换环大小。
那么总的答案为 \(\sum C_{size_i}^{2}\)。
代码：
置换环
void miyan()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
ll ans = 0;
vector<int> id(n + 1, 0);
for (int i = 1; i <= n; ++i)
{
if (id[i])
continue;
ll siz = 0;
int cur = i;
while (id[cur] == 0)
{
++siz;
id[cur] = 1;
cur = a[cur];
}
ans += siz * (siz - 1) / 2;
}
cout << ans << endl;
}并查集
void miyan()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 1; i <= n; ++i)
cin >> a[i];
vector<ll> p(n + 1), siz(n + 1, 1);
for (int i = 1; i <= n; ++i)
p[i] = i;
auto find = [&](auto &&self, int x) -> int
{
if (x != p[x])
p[x] = self(self, p[x]);
return p[x];
};
for (int i = 1; i <= n; ++i)
{
int x = i, y = a[i];
x = find(find, x), y = find(find, y);
if (x != y)
{
siz[x] += siz[y];
p[y] = x;
}
}
ll ans = 0;
for (int i = 1; i <= n; ++i)
if (i == find(find, i) && siz[i] > 1)
ans += siz[i] * (siz[i] - 1) / 2;
cout << ans << endl;
}2. Lucky Permutation
链接：https://codeforces.com/contest/1768/problem/D
题目描述：
给定一个长度为 \(n\) 的排列 \(p\)，每次操作可交换任意两个元素，求最少需要多少次操作，使得最终排列的逆序数恰好为 \(1\)。
思路：
置换环模板题。
最终满足题目要求的情况就是只存在一个大小为 \(2\) 的置换环其余全是大小为 \(1\) 的置换环，并且这个大小为 \(2\) 的置换环中的元素是相邻的（两个元素差为 \(1\)）。
定义 \(cnt\) 为所有置换环所需要的操作次数：
- 当存在相邻两个元素 \((x, x + 1)\) 在同一个置换环中时，那么变成最终状态所需的操作次数就会少一次，最终答案为 \(cnt – 1\)；
- 当不存在相邻两个元素 \((x, x + 1)\) 在同一个置换环中时，那么变成最终状态所需的操作次数就会加一次，既先将数组变成有序排列，再任意交换两个元素，最终答案为 \(cnt + 1\)；
代码：
void miyan()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
int cnt = 0;
vector<int> id(n + 1, 0);
for (int i = 1; i <= n; ++i)
{
if (id[i])
continue;
++cnt;
int cur = i;
while (id[cur] == 0)
{
id[cur] = cnt;
cur = a[cur];
}
}
bool ok = 0;
for (int i = 2; i <= n; ++i)
{
if (id[i] == id[i - 1])
{
ok = 1;
break;
}
}
if (ok)
cout << n - cnt - 1 << endl;
else
cout << n - cnt + 1 << endl;
}