D. Lucky Permutation（置换环）-Toy模板网

这篇具有很好参考价值的文章主要介绍了D. Lucky Permutation（置换环）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

D. Lucky Permutation
严格鸽题解大家可以看看这篇题解，有图片辅助，写的十分的好

题意

题意：给我们一个数长度为n的数组，我们每次操作可以任选两个数进行交换。问我们最后得到满足逆序对是一的序列的最小操作次数是多少。

思路

思路：我们不难知道每次交换两个相邻的数就会形成一个逆序对。

我们考虑置换环，置换环是啥（置换环就是我们对于每一个结点，将其指向排序之后它应该在的地方，直至形成一个环）。

明白置换环什么意思之后，不明白也没关系，我们来举个具体的例子，首先我们给出一个排列 $[1, 3, 4, 5, 2, 6]$ ，那么现在假设我们想让它变成一个单调递增的序列及 $[1, 2, 3, 4, 5, 6]$ ，那对于1和6来说就是一个自环，因为1和6最后指向的位置都是自己。那么3,4,5,2就会形成一个环，及 $2 - > 3 - > 4 - > 5 - > 2$ ，环内有四个点，我们只需要用3步就可以变成单增的序列。也就是说每一个环内相当于只有一个点是不会改变的。那我们的操作次数就是n-环的个数。因为要保证有且仅有一个逆序对我们还得进行一次操作就是任意交换两个相邻的数得到一个逆序对多以操作次数再加1.

我们再考虑一种情况，那就是任意一个置换环内如果有两个数是相邻的，我们能不能省去一步操作呢。答案是可以的，还是上面那个例子，我们现在有一个环是 $[3, 4, 5, 2]$ 我们可以进行一步操作得到 $[3,, 4, 2, 5]$ ，然后我们再进行一步操作可以得到 $[3, 2, 4, 5]$ 那么现在我们观察一下这个序列是不是已经存在了一个 $[3, 2]$ 的逆序对了，那我们就不需要再还原然后交换相邻的位置了。

AC代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int p[N], vis[N];
map<int, int> ring;
int flag;

void dfs(int u)
{
	if (vis[u])
		return;
	vis[u] = 1;
	ring[u] = 1;
	int v = p[u];
	if (ring[u - 1] || ring[u + 1])
		flag = 1;
	dfs(v);
}

void solve()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		vis[i] = 0;
	for (int i = 1; i <= n; i++)
		cin >> p[i];
	int cur = 0;
	flag = 0;
	for (int i = 1; i <= n; i++)
		if (!vis[i])
		{
			cur++;
			ring.clear();
			dfs(i);
		}

	if (flag)
		cout << n - cur - 1 << endl;
	else
		cout << n - cur + 1 << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}