Minimum Cost of Ropes
你有一些绳子，ropes[i] 是第 i 根绳子的长度。你可以将任意两根绳子合并成一根新绳子，新绳子的长度等于两根绳子长度之和，合并的成本也等于这个和。你要不断合并，直到只剩下一根绳子。
编写一个名为 minCostRopes 的函数，返回将所有绳子合并成一根的最小总成本。如果一开始就只有一根绳子，则返回 0。
函数
- ropesinteger-array
- 每根绳子的长度
- 返回值integer
- 将所有绳子合并成一根的最小总成本
约束条件
1 ≤ ropes.length ≤ 1041 ≤ ropes[i] ≤ 100- 答案可以用 32 位有符号整数表示。
示例
- 输入
- ropes = [5, 2, 8, 3]
- 输出
- 33
- 解释
- 将
2和3合并，得到 5；再将两根长度为5的绳子合并，得到 10；然后将8和10合并，得到 18。总和为 5 + 10 + 18 = 33。
- 输入
- ropes = [7]
- 输出
- 0
- 解释
- 只有一根绳子，所以不会发生连接，也不需要支付任何费用。
- 输入
- ropes = [1, 1, 1, 1]
- 输出
- 8
- 解释
- 把
1两两配对，每对成本为 2；然后合并两条长度为2的绳子，成本为 4：总共是 8。把每个1依次加到一条不断变长的绳子上，成本会是 2 + 3 + 4 = 9。
进阶
假设一次连接最多可以合并 3 根绳子，代价是它们的总长度。当绳子数量不能平均分组时，贪心规则该如何调整？
提示
逐个打开提示，每个都会多透露一点。
将总成本写成对原始绳子求和的形式。一根绳子的长度需要支付多少次？
每次连接都会支付绳子的长度费用，因此最长的绳子应该参与最少次数的连接。先连接你手头最短的两根绳子，始终是稳妥的第一步。
将每根绳子放入最小堆中。取出最短的两根，将它们的长度之和加到成本中，再把这个和放回堆中，重复此过程，直到只剩下一根绳子。
题解
每次合并都要支付两段绳子的总长度，因此，较早合并的绳子在之后每次参与合并时，都要再次计入费用。不要让较长的绳子过早参与合并：每轮都合并最短的两段绳子。最小堆可以在 O(log n) 时间内找到这两段绳子。
每轮找出两个最短的
结果正确，但无法在最大的测试中运行完毕
思路
每一轮，扫描绳子堆，找出最短的绳子并取出，再次扫描找出下一根最短的绳子，然后把它们连接后的绳子放回去。
为什么要选两根最短的绳子：把连接过程画成一棵树，绳子就是叶子。一根绳子的长度会为它上方的每次连接付费一次，也就是它的深度。最深的一层有两片并排的叶子，把两根最短的绳子放在那里不会增加成本。因此，某个成本最低的方案会先连接两根最短的绳子，然后在更小的绳子堆上重复这个论证。
总共要进行 n-1 轮，每轮扫描两遍：O(n²)，对于 10^4 根绳子，大约需要进行 10^8 次比较。
算法
- 将绳子复制到工作列表
pile中，并将total初始化为 0。 - 重复以下操作，直到只剩一根绳子：找到最短的绳子，并用最后一根绳子替换它的位置，将其移除。
- 再次执行相同操作，找到下一根最短的绳子。
- 将两根绳子的长度之和加到
total中，并将一根长度为该总和的绳子追加到堆中。 - 返回
total。
def minCostRopes(ropes):
pile = list(ropes)
def take_shortest():
k = 0
for i in range(1, len(pile)):
if pile[i] < pile[k]:
k = i
pile[k], pile[-1] = pile[-1], pile[k] # move it to the end, then remove it
return pile.pop()
total = 0
while len(pile) > 1:
joined = take_shortest() + take_shortest()
total += joined
pile.append(joined)
return total最小堆
思路
最小堆会将最短的绳子放在堆顶，取出堆顶元素或插入一根绳子的时间开销为 O(log n)。一轮包含两次取出操作，为你取出两根最短的绳子，以及一次插入操作，用于插入拼接后的绳子。
n 根绳子需要拼接 n-1 次，每次拼接包含 3 次堆操作，因此时间复杂度为 O(n log n)：对于 10^4 根绳子，大约需要 4 × 10^5 步。堆中最多只会有 n 根绳子。
算法
- 将每根绳子的长度放入最小堆，并设置
total = 0。 - 重复操作，直到只剩一根绳子：取出最短的两根。
- 将它们的长度之和加到
total中，并将这个和放回堆中。 - 返回
total。如果原本只有一根绳子，total会保持为0。
import heapq
def minCostRopes(ropes):
heap = list(ropes)
heapq.heapify(heap) # a min-heap: heap[0] is the shortest rope
total = 0
while len(heap) > 1:
joined = heapq.heappop(heap) + heapq.heappop(heap)
total += joined
heapq.heappush(heap, joined)
return total
易错点和边界情况
- 只排序一次，然后把每根绳子都接到一根不断变长的绳子上。这根绳子的长度可能超过尚未使用的绳子：对于
[2, 3, 4, 4]，代价是 5 + 9 + 13 = 27，而每次连接最短的两根绳子，代价是 5 + 8 + 13 = 26。 - 丢弃接好的绳子。它的长度会回到绳堆中，并在之后的连接中再次计入代价。
- 返回最后一根绳子的长度。对于
[5, 2, 8, 3]，最后一根绳子的长度是 18，但代价是 33。 - 误用了最大堆。除非反转顺序，否则 C++ 的
priority_queue和 Rust 的BinaryHeap会取出最大值。
常见问题3
Minimum Cost of Ropes 的时间复杂度是多少？
使用最小堆，时间复杂度为 O(n log n)，空间复杂度为 O(n)：进行 n-1 次合并，每次包含三次时间复杂度为 O(log n) 的堆操作。每次都扫描整个堆来找出两条最短的绳子，则时间复杂度为 O(n²)。
绳子的最小成本和 Huffman 编码相同吗？
是的，这是同一个算法。Huffman 编码通过反复合并出现频率最低的两个符号来构建前缀码，并使每个频率乘以它在树中的深度后所得的总和最小。在这里，绳子对应符号，绳子的长度对应频率，因此总成本就是同一个总和。
最小成本的绳子问题可以不使用堆来解决吗？
可以，使用两个队列。将绳子排序后放入一个队列，并把每次合并后的绳子放到第二个队列的末尾。合并后的绳子会按非递减顺序排列，因此，剩下的最短绳子会位于其中一个队列的队首。这样每一轮只需 O(1)，长度最大为 100 时，使用计数排序可以将运行时间降至 O(n)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def minCostRopes(ropes):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
ropes = [5, 2, 8, 3]
预期输出
33