让数组有序的最少交换次数

Trick : 让数组有序的最少交换次数

Problem One

1224. 交换瓶子 - AcWing题库

有 N 个瓶子，编号 1∼N，放在架子上。

比如有 5 个瓶子：

2 1 3 5 4

要求每次拿起 2 个瓶子，交换它们的位置。

经过若干次后，使得瓶子的序号为：

1 2 3 4 5

对于这么简单的情况，显然，至少需要交换 2 次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

---

记录每个位置的元素应该去的位置，会形成若干环。对于每个环，内部交换即可，交换次数即为 : 环的长度 - 1 。因为每次交换都会让一个位置有序，环的长度会减 -1。

int const N = 11000;
int n, a[N], to[N], vis[N];void solve(){cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];to[i] = a[i];}int res = 0;for(int i = 1; i <= n; i ++){if(vis[i]) continue ;int len = 0, now = i;while(vis[now] == false){vis[now] = true;len ++;now = to[now];}res += len - 1;}cout << res << '\n';
}

Problem Two

C-Sort4_2024牛客暑期多校训练营4 (nowcoder.com)

Given a permutation${}^{†}$ of length $n$. In one operation, you can choose at most four elements from the permutation and swap their positions arbitrarily. What is the minimum number of operations required to sort the permutation in ascending order?

${}^{†}$ A permutation of length $n$ 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).

---

不用于 Problem One, 本题每次可以选 $4$ 个元素进行位置交换。

我们还是维护交换环，可以发现如下规律 :

对于长度为 $1$ 的交换环，不需要进行操作 ;

对于长度为 $2$ 的交换环，可以每次处理两个 ；

对于长度 $\ge 3$ 的交换环，我们每次操作可以让环的长度减 $3$，直到环的长度 $\le 4$ 时，如果长度为 $3$ 或 $4$ , 一次操作 ；长度为 $2$ 的，统一处理即可。

void solve(){int n;cin >> n;vector<int> a(n + 1), vis(n + 1), to(n + 1);for(int i = 1; i <= n; i ++){cin >> a[i];to[i] = a[i];}int res = 0, s = 0; // s : 2 环的数量for(int i = 1; i <= n; i ++){if(vis[i] || a[i] == i) continue ;int len = 0, now = i;while(vis[now] == false){len ++;vis[now] = true;now = to[now];}if(len % 3 == 2) len -= 2, s ++;else if(len % 3 == 1) len -= 4, res ++;res += len / 3;}cout << res + (s + 1) / 2 << '\n';
}