交换瓶子
来源： 第七届蓝桥杯省赛C++B组,第七届蓝桥杯省赛JAVAA组
题目要求
题目描述：
有 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
思路分析
不愧是暴力杯，其实本题的优化是比较复杂的，但是妙就妙在本题的暴力法居然是可以打满分的，关于暴力的代码不做过多解释，就是遍历两遍数组，在对的位置进行交换即可，本题的优化的思路建议读者好好动手思考，运用了离散数学的相关知识，下面进行讲解：
我们来把这个问题以一种特殊的切入点进行思考：
拿例子来说明：
样例1： 3 1 2 5 4 目标： 1 2 3 4 5
我们按照对应关系进行建图：3 号瓶子现在处于位置1 上，当前位置3 上是 2号瓶子，所以我们从 3 到 2 连一条有向边：
同理，当前 2 号瓶子在 位置3 上，它应该在位置2上，当前位置2 上是 1 号瓶子，故从 2 到 1 连一条有向边：
按照上述说法，读者自行对样例1进行建图，结果如下图所示：
现在我们来交换 1 号瓶子和 3 号瓶子，即我们变成了：
```cpp 样例1： 1 3 2 5 4 目标： 1 2 3 4 5
重复上述建图：
可以看出，交换一个环的元素的结果就是把一个环拆成了两个环，那么交换两个环的元素，其实就是让两个环进行了合并操作：可以理解成上述操作的逆操作。
而我们最终想要得到的，其实就是让 1 , 2 , 3 , 4 , 5分别独立成环，即我们要对一个环内的元素进行不断交换：让一个大环不断的拆分为两个小环，直到每个环均只有一个元素。
代码 (暴力)
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 10010; int b[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i ++ ) cin >> b[i]; int cnt = 0; for (int i = 1; i <= n; i ++ ) if (b[i] != i) for (int j = 1; j <= n; j ++ ) if (b[j] == i) { swap(b[j], b[i]); cnt ++; break; } cout << cnt << endl; return 0; }
代码 (置换群)
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 10010; int b[N]; bool st[N]; int main() { int n; 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 << endl; return 0; }
