2016年蓝桥杯省赛B组交换瓶子题解（洛谷P8637）| 解题思路与代码优化
3天前
一、题目解读
题目要求将N个瓶子通过交换操作使其编号与位置对应（即每个瓶子指向自身）。每个瓶子初始指向另一个瓶子位置，需计算最小交换次数。例如，当瓶子i指向瓶子j时，交换i与j的位置可使两者指向自身。题目关键在于识别环形结构并计算交换次数。
二、解题思路
并查集（Union-Find）思想优化解题：
1. 将每个瓶子视为节点，初始各节点自成环。
2. 遍历时标记已访问节点，识别出每个连通环（即闭合路径）。
3. 每个环的交换次数为环大小-1（最后一个节点无需交换）。
4. 累加所有非单节点环的交换次数，得到最终结果。
核心在于利用环结构特性减少无效交换计算。
三、解题步骤
1. 输入处理：读取N及每个瓶子的指向位置，存储于bottles数组（1-based索引）。
2. 初始化标记：使用visited数组记录节点是否被遍历。
3. 循环遍历：
对每个未访问节点i，启动新环遍历。
通过while循环跟踪链i → bottles[i] →...直至回到起点（形成环）。
标记路径上所有节点，记录环大小cycleSize。
4. 交换次数计算：若环大小>1，则需cycleSize-1次交换（单节点环无需交换）。
5. 输出结果：累加所有环的交换次数并输出。
四、代码与注释
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> bottles(N + 1); // 使用1-based索引
vector<bool> visited(N + 1, false);
// 读取输入
for (int i = 1; i <= N; ++i) {
cin >> bottles[i];
}
int swapCount = 0;
// 遍历每个瓶子
for (int i = 1; i <= N; ++i) {
if (!visited[i]) { // 未访问节点为新环起点
// 开始一个新的环
int current = i;
int cycleSize = 0;
// 遍历整个环
while (!visited[current]) {
visited[current] = true; // 标记已访问
current = bottles[current]; // 跟踪指向节点
cycleSize++; // 环大小+1
}
// 每个大小为k的环需要k-1次交换
if (cycleSize > 1) {
swapCount += (cycleSize - 1);
}
}
}
cout << swapCount << endl;
return 0;
}注释说明：
● visited数组用于避免重复遍历已处理的环。
● cycleSize记录当前环的节点数，通过累加遍历次数计算。
● 最终交换次数仅累加非单节点环的贡献，避免冗余计算。
五、总结
本解法通过并查集思想将问题转化为环计数，有效降低时间复杂度。关键在于识别闭合路径并优化交换次数计算逻辑。代码简洁且易于理解，适用于处理具有环形结构的交换问题。掌握此类算法思维对编程竞赛中复杂路径问题的解决具有重要价值。
原创内容 转载请注明出处
