Pythonでリストを1つの整数に減らすための最小コストを見つけるプログラム

numsという番号のリストがあるとします。任意の2つの数値を取得し、それらを削除して、最後にそれらの合計を追加することにより、numの長さを減らすことができます。この操作を実行するためのコストは、削除した2つの整数の合計です。 numsを1つの整数に減らすための最小の総コストを見つける必要があります。

したがって、入力が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の場合、do
  • a：=ヒープ数の最上位要素
  • b：=ヒープ数の最上位要素
  • ans：=ans + a + b
  • ヒープ番号にa+bを挿入します
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

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