本文主要是介绍D. Lucky Permutation 置换环，仅有一个连续的逆序的理解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem - D - Codeforces
D. Lucky Permutation（置换环）-CSDN博客
如果环中，有相邻的两个点，那么可以通过减少一次交换，使得其贡献出一个逆序对。
感觉这个博客对于最后逆序说的还是不太好理解，这个结论如何证明呢？
枚举情况理解：
2 1 3 4
连续的数如果“被动归位”（置换环的数都是主动回到自己位置），说明环内没有别的数了，只有环内其余数都归位，这个没动过数才会归位。（所以n-1次）
就对1 2 来说吧，1,2在环中时
如果不动 1 2，他们永不归位，最后会到对方的位置，正好符合一个连续逆序对。
（自己想想，）
——————
环是越来越小的，每次交换两个数是为了让一个数回自己的位置，如果另一个数也回去了，说明只剩两个数了。
1,2可能不在环内连着，但是慢慢的会靠近。
map<int, bool>ring;void solve()
{int n;cin >> n;vector<int>arr(n + 1);vector<int>vis(n + 1);int flag = 0;for (int i = 1; i <= n; i++){cin >> arr[i];}int ans = 0;for (int i = 1; i <= n; i++){if (vis[i] || arr[i] == i)continue;int cur = i;int tmp = 0;ring.clear();while (vis[cur] == 0){vis[cur] = 1;ring[cur] = 1;if (ring[cur + 1] || ring[cur - 1]){flag = 1;}cur = arr[cur];tmp++;}ans += tmp - 1;}if (flag)cout << ans - 1 << endl;elsecout << ans + 1 << endl;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}这篇关于D. Lucky Permutation 置换环，仅有一个连续的逆序的理解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
