原题链接：交换瓶子

题目描述

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

比如有 $5$ 个瓶子：

2 1 3 5 4

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

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

1 2 3 4 5

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

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

输入格式

第一行包含一个整数 $N$，表示瓶子数量。

第二行包含 $N$ 个整数，表示瓶子目前的排列状况。

输出格式

输出一个正整数，表示至少交换多少次，才能完成排序。

数据范围

$1≤N≤10000,$

输入样例1：

5
3 1 2 5 4

输出样例1：

3

输入样例2：

5
5 4 3 2 1

输出样例2：

2

贪心写法

遍历整个数组，只需要选出后面的比它小的最小值，交换即可，统计交换次数，类似于选择排序

时间复杂度

$O(n^2)$

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 10010;
int w[N];
int n;

int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++) scanf("%d",&w[i]);

    int res = 0;
    for(int i = 0;i < n;i ++) {
        int idx = i;
        for(int j = i + 1;j < n;j ++) {
            if(w[j] < w[idx]) 
                idx = j;
        }
        if(idx != i) {
            res ++;
            swap(w[idx],w[i]);
        }
    }
    cout << res << endl;
    return 0;
}

利用环来优化

可以建立一个图

那么利用这种方法建立的图，每个点的入度和从出度都为 $1$，且点的个数和边的个数都为 $n$

那么这种图必定是不同的环

最终结果是要位置上的值和位置的值相等，那么图像就是 $n$ 个不同的自环

我们要求的就是用最少的次数，来达到将上述图转换为 $n$ 个不同的自环

所以可以得出

• 如果在环内交换，那么环必定会分裂为两个环
• 如果是不同的环交换，那么两个环必定会合成一个环

可以证得，如果不同得环数是 $k$ ，那么最小的次数必定是 $n - k$

如果 $k < n$，那么存在环有两个或两个以上的节点，那么我们必定可以经过一次操作将该环分裂出一个环，得到 $k + 1$

所以最小的交换次数就是 $n - k$

时间复杂度

$O(n)$

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 10010;
int b[N];
bool st[N];
int n;

int main()
{
    scanf("%d",&n);

    for(int i = 1;i <= n;i ++) scanf("%d",&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;
        }
    }

    printf("%d\n",n - cnt);
    return 0;
}