翻译

有n个盒子，第一个盒子里有很多球，球有n种颜色。每次可以选择取出一个盒子里所有的球，放入两个或者三个盒子里面，成本是选择的盒子里的球的个数。求需要花多少成本把球分别放入对应颜色的盒子。

分析

这道题是的过程就是自顶向下构建一颗树，要求这棵树的带权路径长度最小。根据这个世界上不存在的公司开发的一个不存在的搜索引擎得知，哈夫曼树 的带权路径长度最小。而三叉哈夫曼树是优于二叉哈夫曼树的，所以这道题的答案是 三叉哈夫曼树的带权路径长度 。

逻辑

哈夫曼树的构建过程是自底向上的，每次都选三个值最小的节点，合并成一个新的节点放回去，如此循环，直到只剩最后一个节点也就是根节点。

在节点数量是偶数的情况下，最后一次合并只会有两个节点，为了优化这种情况，需要在节点数量是偶数的时候开始前添加一个0节点，这样保证三叉树的唯一一个二叉在叶子节点，可以得到最优解。

上述过程，用到了 优先队列 ，每次都取值最小的前三个值。

代码(Python2)

提交记录

import heapq

n = int(raw_input())
aList = raw_input().split()

ai = []
for a in aList:
    ai.append(int(a))

if len(ai)%2 == 0:
    ai.append(0)

heapq.heapify(ai)

sum = 0
while len(ai) > 1:
    a = heapq.heappop(ai)
    b = heapq.heappop(ai)
    c = heapq.heappop(ai)
    sum += a + b + c
    heapq.heappush(ai, a + b + c)

print sum