2016年蓝桥杯省赛B组（洛谷P8637）：用环分解理论破解最少交换次数难题

8个月前 (06-25)比赛题解404

引言

在算法竞赛中，排列相关的问题非常常见。今天我们要探讨的"交换瓶子"问题就是一个典型的排列问题，它看似简单，却蕴含着深刻的数学原理。通过这个问题，我们可以学习如何将实际问题转化为数学模型，并找到高效的解决方案。

一、问题重述

我们有N个编号为1-N的瓶子，初始时以任意顺序排列。每次操作可以选择任意两个瓶子交换它们的位置。我们的目标是通过最少的交换次数，使瓶子按编号升序排列。

二、问题转化

这个问题可以转化为排列的排序问题。我们可以将瓶子的排列看作一个置换，例如：
初始排列：[2,1,3,5,4]
可以表示为置换：1→2, 2→1, 3→3, 4→5, 5→4

三、关键观察

‌排列的环分解‌：任何排列都可以分解为若干个不相交的环。例如上面的例子可以分解为两个环：(1,2)和(4,5)，以及一个自环(3)。
‌交换次数与环的关系‌：对于一个大小为k的环，最少需要k-1次交换才能将其归位。例如环(1,2)需要1次交换，环(4,5)也需要1次交换。
‌总交换次数‌：所有环的(k-1)之和就是最少需要的交换次数。

四、算法步骤详解

‌初始化‌：创建一个访问数组来记录哪些元素已经被处理过。
‌环检测‌：对于每个未被访问的元素，沿着它的值指向的位置继续查找，直到回到起点，形成一个环。
‌计数‌：对于每个检测到的环，将其大小减1加到总交换次数中。
‌输出结果‌：最终的总交换次数就是答案。

五、实现解析

‌输入处理‌：使用1-based索引读取瓶子排列，方便直接对应编号。
‌环检测‌：使用visited数组避免重复处理，current变量跟踪当前访问的位置。
‌环大小计算‌：cycleSize变量记录环中元素个数。
‌交换次数累加‌：对于每个环，将cycleSize-1加到总交换次数中。

六、完整代码

#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++;
            }
            
            // 每个大小为k的环需要k-1次交换
            if (cycleSize > 1) {
                swapCount += (cycleSize - 1);
            }
        }
    }
    
    cout << swapCount << endl;
    return 0;
}