「POI2009 R1」大象 Elephants 题解

问题分析

我们有 $n$ 头大象，每头大象有各自的体重 $m_i$。它们当前排成一个序列 $a$，需要重新排列成目标序列 $b$。每次可以交换任意两头大象的位置，交换成本为两头大象的体重之和。要求找到总成本最小的交换方案。

这是一个典型的带权最小交换排序问题。

关键观察

1. 排列的循环分解

将当前排列到目标排列的变换看作一个置换 $\pi$，其中 $\pi(i)$ 表示当前在位置 $i$ 的大象应该去的位置。

这个置换可以分解为若干个不相交的循环。每个循环代表一组需要循环移动的大象。

2. 循环内的最小成本策略

对于一个包含 $k$ 个元素的循环，有两种主要的交换策略：

策略1：循环内交换

• 使用循环内最轻的大象作为"媒介"
• 进行 $k-1$ 次交换
• 总成本 = $\text{sum} + (k-2) \times \text{min\_in\_cycle}$

策略2：借助全局最轻

• 引入全局最轻的大象辅助交换
• 总成本 = $\text{sum} + \text{min\_in\_cycle} + (k+1) \times \text{global\_min}$

其中：

• $\text{sum}$ 是循环内所有大象的体重和
• $\text{min\_in\_cycle}$ 是循环内最轻大象的体重
• $\text{global\_min}$ 是所有大象中最轻的体重
• $k$ 是循环的大小

3. 策略选择

对于每个循环，我们选择两种策略中成本较小的那个：

$$\text{cost} = \min(\text{sum} + (k-2) \times \text{min\_in\_cycle},\ \text{sum} + \text{min\_in\_cycle} + (k+1) \times \text{global\_min}) $$

算法步骤

步骤1：预处理

1. 读取输入数据：$n$, $m[1..n]$, $a[0..n-1]$, $b[0..n-1]$
2. 建立位置映射：对于目标排列 $b$，记录每个大象应该在的位置 $pos$

步骤2：寻找全局最小值

遍历所有大象的体重，找到全局最小值 $global\_min$。

步骤3：循环分解与成本计算

1. 初始化访问标记数组 $visited$
2. 遍历每个位置 $i$：
   • 如果 $i$ 未被访问，开始一个新的循环
   • 遍历整个循环，记录：
     • 循环大小 $cycle\_size$
     • 循环内大象体重和 $cycle\_sum$
     • 循环内最轻体重 $cycle\_min$
3. 如果 $cycle\_size > 1$，计算该循环的最小成本并累加

步骤4：输出结果

输出所有循环成本的总和。

正确性证明

策略1的正确性

在循环内使用最轻元素作为媒介：

• 进行 $k-1$ 次交换
• 每次交换都涉及最轻元素
• 总交换次数最少，且利用了循环内的最轻元素

策略2的正确性

当全局最轻元素比循环内最轻元素轻很多时：

• 引入全局最轻元素可以降低交换成本
• 虽然交换次数增加，但每次的成本可能更低

最优性

可以证明，对于任意循环，最优解一定是这两种策略之一。

复杂度分析

• 时间复杂度：$O(n)$
  • 预处理：$O(n)$
  • 寻找全局最小值：$O(n)$
  • 循环分解：每个位置只被访问一次，$O(n)$
• 空间复杂度：$O(n)$
  • 存储体重数组：$O(n)$
  • 存储排列和位置映射：$O(n)$
  • 访问标记数组：$O(n)$

样例分析

输入

6
2400 2000 1200 2400 1600 4000
1 4 5 3 6 2
5 3 2 4 6 1

循环分解

建立映射关系：

• 大象1应该在位置5
• 大象4应该在位置3
• 大象5应该在位置0
• 大象3应该在位置1
• 大象6应该在位置4
• 大象2应该在位置2

得到循环：

• 循环1：位置0 → 位置5 → 位置2 → 位置0（大象1, 2, 5）
• 循环2：位置1 → 位置3 → 位置1（大象4, 3）

成本计算

全局最小值：$global\_min = 1200$

循环1（大小3）：

• 体重和：$2400 + 2000 + 1600 = 6000$
• 循环内最小值：$1600$
• 策略1：$6000 + (3-2) \times 1600 = 7600$
• 策略2：$6000 + 1600 + (3+1) \times 1200 = 7600 + 4800 = 12400$
• 选择策略1：$7600$

循环2（大小2）：

• 体重和：$2400 + 1200 = 3600$
• 循环内最小值：$1200$
• 策略1：$3600 + (2-2) \times 1200 = 3600$
• 策略2：$3600 + 1200 + (2+1) \times 1200 = 4800 + 3600 = 8400$
• 选择策略1：$3600$

总成本：$7600 + 3600 = 11200$

与样例输出一致。

实现细节

1. 索引处理：注意数组索引从0开始还是从1开始
2. 数据类型：使用 long long 避免整数溢出
3. 输入输出优化：使用 ios_base::sync_with_stdio(false) 加速
4. 循环检测：使用标记数组避免重复访问

总结

本题的核心在于将排列排序问题转化为循环分解问题，然后为每个循环选择最优的交换策略。通过数学分析，我们发现只需要比较两种策略即可得到最优解，从而在 $O(n)$ 时间内解决问题。

这种将组合优化问题转化为数学计算的方法在竞赛中非常常见，关键在于发现问题的内在结构和数学性质。