hh的蓝桥杯每日一题（交换瓶子）

15.交换瓶子 - 蓝桥云课

方法一：贪心做法

• 对于位置 i，如果 a[i] ≠ i

• 就把 a[i] 和 a[a[i]] 交换（把当前数字放到它应该去的位置）

• 这样每次交换都能让至少一个数字归位

• 重复直到 a[i] = i

#include<iostream> using namespace std; const int N = 10010; int n; int a[N]; int main() { cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; } int ans = 0; // 贪心：直接把每个数放到正确位置 for(int i = 1; i <= n; i++) { while(a[i] != i) { // 如果当前位置的数不对 swap(a[i], a[a[i]]); // 把它和它应该在的位置交换 ans++; } } cout << ans << endl; return 0; }

方法二：利用环的性质（交换排序最小交换问题）

这个问题实际上可以转化为图论中的环分解问题：

• 把排列看作一个置换（permutation）

• 每个元素应该回到它的正确位置（值 i 应该在位置 i）

• 通过交换操作，我们可以将排列分解为若干个环

• 最小交换次数 = 所有环的大小之和 - 环的个数

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 10010; // 题目说 N<10000，所以开大一点 int n; int a[N]; bool st[N]; // 标记数组，记录位置是否访问过 int main() { cin >> n; for(int i = 1; i <= n; i++) // 注意：题目瓶子编号从1开始 { cin >> a[i]; } int ans = 0; // 遍历所有位置 for(int i = 1; i <= n; i++) { // 如果当前位置的值不是 i，且没有被访问过 if(a[i] != i && !st[i]) { // 找到当前元素所在的环 int j = i; int cnt = 0; // 环的大小 while(!st[j]) { st[j] = true; // 标记已访问 j = a[j]; // 跳到这个位置应该放的元素的位置 cnt++; } // 环的大小为 cnt，需要 cnt-1 次交换 ans += (cnt - 1); } } cout << ans << endl; return 0; }