Python程序：将列表归约为单个整数的最小成本

假设我们有一个名为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，我们将得到20。所以总和是45。

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

  • 使用nums中的元素创建一个堆。
  • ans := 0
  • 当nums的大小>= 2时，执行以下操作：
    • a := 堆nums的最顶端元素
    • b := 堆nums的最顶端元素
    • ans := ans + a + b
    • 将a+b插入堆nums
  • 返回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))

输入

[2, 3, 4, 5, 6]

输出

45

更新于：2020年10月19日

720 次查看

开启你的职业生涯

完成课程后获得认证

开始学习
广告