#H. 重编码

传统题

2000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

最优二又树：带权路径长度WPL（Weighted Path Length）最小的二叉树，也称Huffman树。

结点的带权路径长度：在一棵树中，如果其结点上附带有一个权值，通常把该结点的路径长度与该结点上的权值之积称为该结点的带权路径长度。

有一篇文章，文章包含 n 种单词，单词的编号从 1 至 n，第 i 种单词的出现次数为 w[i]。

现在，我们要用一个 2 进制串 s[i] 来替换第 i 种单词，使其满足如下要求：对于任意的 1≤i,j≤n（i≤j），都有s[i]不是s[j]的前缀。

你的任务是对每个单词选择合适的 s[i]，使得替换后的文章总长度（定义为所有单词出现次数与替换它的二进制串的长度乘积的总和）最小。

第一行一个整数 n，表示单词种数。(0 < n < $20^6$ )

后面的n行，每行为一个正整数 w[i]，表示第 i 种单词的出现次数。(1 < w[i] < 80000)

输出一个整数，表示整篇文章重编码后的最短长度。

题意：求最优二叉树的带权路径长度

对于测试样例，一种最优方案是令 s[1]=000，s[2]=001，s[3]=01，s[4]=1。这样文章总长即为 3*1+3*1+2*2+1*2=12。

另一种最优方案是令 s[1]=00，s[2]=01，s[3]=10，s[4]=11。这样文章总长也为 12。

堆 Huffman树