CF1768D Lucky Permutation Solution

CF1768D 题意不再简述。

首先题目要求变成逆序对只有一个的排列，也就是说，我们可以先考虑将一个排列通过交换元素变成另一个排列最小的步数，我们可以将两个排列相同位置上的数连边，很显然会形成几个环，若排列长度为 \(n\)，形成 \(t\) 个环，每个环长为 \(len_i\)，则每个环交换完至少是依次交换，也就是总共需要 \(\sum_{i=1}^t (len_i-1)=n-t\)。所以求出步数是 \(O(n)\) 的。

然后，题目要求变成的目标排列是逆序对只有一个，也就是目标排列是将升序排列中一对相邻元素交换后得到的，显然就有一个 \(O(n^2)\) 的算法：枚举交换的相邻元素，计算出步数然后取最小值。

然而这并不能过此题，考虑优化，我们交换操作至多会影响两个环，也就是说，我们先对原序列和生序序列之间处理出环，然后考虑交换的位置，设交换的两个位置是 \(i\) 和 \(i+1\)，通过手玩可以发现：当 \(i\) 和 \(i+1\) 在同个环内时，交换操作会把这个环一分为二，总步数会减一；反之，当 \(i\) 和 \(i+1\) 在不同环内时，交换操作会把两个环合二为一，总步数加一。所以我们通过并查集维护是否在同环之内，先预处理出原序列与升序序列之间的环，然后考虑交换操作，\(O(1)\) 求出每次交换后总答案，最后取最小值，时间复杂度 \(O(n)\)。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5 + 10;

int n, A[N], T[N], id[N], bel[N], fa[N], cnt[N];

int Find(int x) {
	if (fa[x] == x) return x;
	return fa[x] = Find(fa[x]);
}

int main() {
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int _; cin >> _;
	while (_ --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) {
			cin >> A[i]; fa[i] = i; cnt[i] = 1;
		}
		for (int i = 1; i <= n; i ++) {
			if (Find(A[i]) != Find(i)) {
				cnt[Find(i)] += cnt[Find(A[i])]; cnt[Find(A[i])] = 0;
				fa[Find(A[i])] = Find(i);
			}
		}
		int S = 0, Ans = 1e9;
		for (int i = 1; i <= n; i ++) 
			if (fa[i] == i) S += cnt[i] - 1;
		for (int i = 1; i < n; i ++) {
			if (Find(i) == Find(i + 1)) Ans = min(Ans, S - 1);
			else Ans = min(Ans, S + 1);
		}
		cout << Ans << "\n";
	}
	return 0;
}