【题解】交换瓶子

题目链接：交换瓶子

关于题目

1. 相似题目： 小朋友排队 。 由于小朋友排队这道题只能交换 相邻 的两个数字，所以交换次数最多是 $n^2$ ，具体数量等于序列逆序对的数量。
2. 本题由于可以交换 任意两个位置 的数字，所以交换次数最多是 n - 1 。

置换群

1. 将 每个点向其目标位置上的点连一条边，称这样的一个环为 置换 ，序列中所有这样的置换称为一个 置换群 。
2. 将置换中某个点与其目标位置上的点交换位置，原来的一个环将会分裂为两个新的环。如果将两个不同的置换上的点交换位置，则两个置换将合并为一个新的环。
3. 如果所有数字都在自己的目标位置，则会得到 n 个置换，也即 n 个环。所以目标是得到 n 个环。
4. 设所给序列初始的置换群中环的个数为 k ，由于每交换一个环中的两个位置，就会得到两个新的环，所以最少交换 n - k 次就可以得到 n 个环。

环的数量

1. 如何确定序列初始时环的数量？需要用一个标记数组，从前向后遍历序列，如果当前点没有被遍历过，说明找到一个新的环，标记该点并将该点所在环的所有点依次标记。

法一：暴力枚举

c++ 333ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second


const int N = 1e4 + 10;

int n;
int a[N];

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

    int sum = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (a[i] == i) continue;
        for (int j = i + 1; j <= n; j ++ )
        {
            if (a[j] == i) 
            {
                swap(a[i], a[j]);
                sum ++ ;
                break;
            }
        }
    }

    cout << sum << endl;
    return 0;
}

法二：置换群

c++ 线性 20ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second


const int N = 1e4 + 10;

int n;
int b[N];
bool st[N];

int main()
{
    cin >> 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;
        }
    }

    cout << n - cnt << endl;
    return 0;
}