代码收藏家技术教程 2天前

第十六届蓝桥杯省赛PythonB赛道：书架还原之从零开始编写代码

本文是对“非线性结构优化”问题的思路拆解。

一、试题回顾

本题考察：图论

二、还原出原始题意

给定一个长度为 n 的排列（所有元素为 1 到 n 的某个顺序排列），你可以交换任意两个位置的元素。你需要计算出将这个排列变为升序排列所需要的最少交换次数。

举个例子：

排列 = [2, 3, 4, 5, 1]

目标：变成 [1, 2, 3, 4, 5]，最少交换几次？

三、建模问题

面对的输入是一个“乱序的排列”，目标是将它变成“升序的排列”；

“交换任意两个数”，代价是“1 次操作”；

所以我们希望找到最少的操作步骤。

每个位置应该放什么？

→ 索引 i 处应放的是 i+1。

所以，不妨把排列视为一个“目标位置错乱”的集合。

如果一个数 x 出现在了不属于它的位置上，会发生什么？

        它原本应该在 x−1的位置上。

        而现在可能是 a[x−1]=y，所以这就意味着：

        数 x 应该去 x−1，但 x−1 处又放着 y，而 y 也不在它该在的地方……

        这是不是在形成一条“路径”或者说“链条”？

本质：一个置换 = 若干个置换环（cycle）

观察这个排列 [2, 3, 4, 5, 1]

发现什么了吗？

这是一个环：

0 → 1 → 2 → 3 → 4 → 0

这说明，我们可以通过不断交换，把这个环“拆开”成正确位置。

让我们来构造一次环的“还原过程”：

一个长度为 k 的环：a1→a2→⋯→ak→a1

我们希望把每个元素放回它应该在的位置上。

可以使用如下操作：

        固定其中一个元素（比如 a1），然后将其它元素依次换到它们正确的位置上；

        每次操作“修正”一个位置，总共需要 k−1次操作。

        就像拼魔方那样，我们只动一块基准，然后围绕它排好其他块。

四、算法演示

1.将输入排列看作一个置换；

2.找到其中所有的置换环（cycle）；

3.对每一个长度为 k 的环，需要 k−1次交换；

4.将所有环的最小交换次数累加。

五、用图论的视角来重新理解

六、代码呈现

n = int(input())
lst = list(map(int, input().split()))
visited = [False] * n
ans = 0

for i in range(n):
    if not visited[i]:
        cycle_size = 0
        j = i
        while not visited[j]:
            visited[j] = True
            cycle_size += 1
            j = lst[j] - 1
        ans += (cycle_size - 1)

print(ans)  #Ciii^x

AI注释版：

n = int(input())
lst = list(map(int, input().split()))

# 创建一个长度为 n 的布尔型列表 visited，用于标记列表中的元素是否已经被访问过
# 初始时，所有元素都标记为未访问（False）
visited = [False] * n

# 初始化一个变量 ans，用于存储最终的结果
ans = 0

# 遍历列表中的每个元素
for i in range(n):
    # 如果当前元素 i 还未被访问过
    if not visited[i]:
        # 初始化一个变量 cycle_size，用于记录当前循环的大小
        cycle_size = 0
        # 从当前元素 i 开始进行循环遍历
        j = i
        # 当当前元素 j 还未被访问过时，继续循环
        while not visited[j]:
            # 标记当前元素 j 为已访问
            visited[j] = True
            # 循环大小加 1
            cycle_size += 1
            # 更新 j 为 lst[j] - 1，继续在循环中移动
            j = lst[j] - 1
        # 对于每个循环，需要的操作次数为循环大小减 1
        # 将当前循环所需的操作次数累加到结果 ans 中
        ans += (cycle_size - 1)

print(ans)