用 Python 编写程序，查找将列表缩减为一个整数的最低成本

pythonserver side programmingprogramming更新于 2026/2/2 6:04:17

假设我们有一个名为 nums 的数字列表。我们可以通过取任意两个数字、删除它们并在末尾附加它们的和来减少 nums 的长度。执行此操作的成本是我们删除的两个整数的总和。我们必须找到将 nums 缩减为一个整数的最小总成本。

因此，如果输入为 nums = [2, 3, 4, 5, 6]，则输出将为 45，因为我们取 2 和 3 然后移除以获得 [4, 5, 6, 5]，然后我们取 4 和 5 然后移除以获得 [6, 5, 9]，然后取 6 和 5，然后移除它们，我们得到 [9, 11]，最后移除 9 和 11，我们将得到 19。所以总和是 45。

为了解决这个问题，我们将遵循以下步骤 −

使用 nums 中存在的元素创建堆
ans := 0
当 nums 的大小 >= 2 时，执行
- a := 堆数的最顶部元素
- b := 堆数的最顶部元素
- ans := ans + a + b
- 将 a+b 插入到堆数中
返回 ans

让我们看看下面的实现以便更好地理解 −

示例

class Solution:
   def solve(self, nums):
      import heapq
      heapq.heapify(nums)
      ans = 0
      while len(nums) >= 2:
         a = heapq.heappop(nums)
         b = heapq.heappop(nums)
         ans += a + b
         heapq.heappush(nums, a + b)
      return ans
ob = Solution()
nums = [2, 3, 4, 5, 6]
print(ob.solve(nums))