摘要
Title: 148. 合并果子
Tag: Huffman树、优先队列
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

148. 合并果子

• 题意

  假定每个果子重量都为 1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使达达耗费的体力最少，并输出这个最小的体力耗费值。

• 思路

  经典哈夫曼树的模型，每次合并重量最小的两堆果子即可

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-15 15:50:29
  FilePath: \ACM\Acwing\148.py
  LastEditTime: 2022-03-15 15:50:29
  '''
  from heapq import heappush, heappop
  
  n = int(input())
  q = []
  nums = map(int, input().split())
  
  for num in nums:
      heappush(q, num)
  
  ans = 0
  while len(q) > 1:
      a = heappop(q)
      b = heappop(q)
      ans += (a + b)
      heappush(q, a + b)
  print(ans)