C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

法一：

思路：

暴力

$1、枚举每个位置$

$2、如果此位置上的瓶子序号a[i]与位置号i不同，从这个位置的下一个位置开始枚举，找到与$
$这个位置号对应的瓶子序号a[j]，交换一下这两个瓶子即可$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e4 + 10;

int n;
int a[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];

    int sum = 0;
    for (int i = 1; i <= n; i ++) 
        if (a[i] != i) {
            for (int j = i + 1; j <= n; j ++) // 枚举
                if (a[j] == i)
                    swap(a[i], a[j]);

            sum ++; // 记录交换次数       
        }

    cout << sum;

    return 0;
}

还是暴力法好懂啊，暴力yyds

法二：

思路：

环，图论，置换群

$图解：$

$时间复杂度：O(n)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e4 + 10;

int n;
int b[N];
bool st[N]; // 帮助找环

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> b[i];

    int cnt = 0;
    for (int i = 1; i <= n; i ++) 
        if (!st[i]) { // 当前这个点没有被找过
            cnt ++; // 说明它在一个新环里面
            for (int j = i; !st[j]; j = b[j])
                st[j] = true;
        }

    cout << n - cnt;

    return 0;
}