C++ 中连接 n 根绳子所需的最少成本

概述

给定 n 根长度不一的绳子，我们需要将所有这些绳子合并成一根。合并任意两根绳子会产生相当于这两根绳子长度之和的成本。目标是最小化合并所有绳子的总成本。这是一个经典的贪心算法问题，可以使用优先队列（最小堆）高效地解决。

方法

该问题可以简化为重复地先连接两根最短的绳子，因为这样可以最小化每一步的中间成本。使用最小堆，我们可以高效地提取出最短的两根绳子，计算它们的和，然后将结果绳子插回堆中。重复此过程，直到堆中只剩下一根绳子。

解决步骤

1. 将所有绳子的长度推入一个最小堆中。
2. 当堆中的绳子数量大于一时：
   • 提取出两根最短的绳子。
   • 计算它们的成本（长度之和）。
   • 将此成本加到总成本中。
   • 将结果绳子推回堆中。
3. 最终的总成本就是连接所有绳子的最小成本。

为什么要使用最小堆？

最小堆能高效地支持：

• 提取最小值：以 O(log⁡n)O(\log n)O(logn) 的时间复杂度检索最小元素。
• 插入：以 O(log⁡n)O(\log n)O(logn) 的时间复杂度添加新元素。

贪心方法确保我们首先合并最短的绳子，从而最小化每一步的增量成本。

算法复杂度

1. 堆的构建： O(n)O(n)O(n)，其中 nnn 是绳子的数量。
2. 堆操作： 对于 n−1n-1n−1 次合并操作：
   • 提取最小值（每次合并 2 次操作）： O(log⁡fon)O(\log⁡⁡ n)O(logn)。
   • 插入（每次合并 1 次操作）： O(log⁡fon)O(\log n)O(logn)。
   • 总计： O((n−1)⋅logfo⁡n)O((n-1) \cdot \log n)O((n−1)⋅logn)。

因此，总时间复杂度为 O(n⋅log⁡fon)O(n \cdot \log n)O(n⋅logn)，这对于解决此问题非常高效。

示例

让我们用一个例子来说明如何在 C++ 中以最小成本连接 n 根绳子。

输出

Minimum cost to connect ropes: 29   

代码说明

1. 初始化
   • 我们通过使用自定义比较器 greater<int> 创建一个 priority_queue 来构建一个最小堆。
   • 最初将绳子推入最小堆。
2. 堆操作
   • 使用 minHeap.top() 和 minHeap.pop() 取出两个最小的元素。
   • 计算连接两根绳子的成本并加到总成本中。
   • 将结果绳子推回堆中。
3. 终止
   • 循环继续，直到堆中只剩下一个元素，这表示最后一根连接好的绳子。
4. 输出
   • 变量 totalCost 存储了连接所有绳子的最小成本。

示例演算

输入： ropes = {4, 3, 2, 6}

分步执行

1. 初始化最小堆：{2, 3, 4, 6}
2. 提取两个最小的：2, 3
   • 合并 2+3=52 + 3 = 52+3=5
   • 将 5 推回堆中 {4, 6, 5}
   • 总成本 0+5=50 + 5 = 50+5=5
3. 提取两个最小的：4, 5
   • 合并 4+5=94 + 5 = 94+5=9
   • 将 9 推回堆中 {6, 9}
   • 总成本 5+9=145 + 9 = 145+9=14
4. 提取两个最小的：6, 9
   • 合并 6+9=156 + 9 = 156+9=15
   • 将 15 推回堆中 {15}
   • 总成本 14+15=2914 + 15 = 2914+15=29
5. 堆中只剩一根绳子：{15}

输出： 最小成本 = 29

边缘情况

1. 单根绳子
   • 输入：{10}
   • 输出：成本 = 000（无需连接）。
2. 两根绳子
   • 输入：{5, 10}
   • 输出：成本 = 5+10=155 + 10 = 155+10=15。
3. 大量绳子
   • 输入：包含随机值的大数组。
   • 由于 O(n⋅log⁡n)O(n \cdot \log n)O(n⋅logn) 的复杂度，该算法能高效处理大量输入。

应用

贪心策略的几个应用如下

1. 霍夫曼编码

• 同样的贪心策略用于构建霍夫曼树以进行数据压缩。

2. 网络电缆合并

• 以最小成本连接网络电缆。

3. 文件合并

• 在分布式系统中以最小成本将多个文件合并为一个文件。

优化技巧

• 对于涉及重复提取最小元素的问题，始终使用最小堆。
• 避免在每一步手动对数组进行排序，因为这会将时间复杂度增加到 O(n2)O(n^2)O(n2)。