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 次檢視

開啟你的職業生涯

完成課程後獲得認證

開始學習
廣告