1387: Huffman Tree

题目

题目描述

给定N个权重作为叶子节点，请你构建一棵哈夫曼树。

输入格式

输入文件N+1行。

第一行包括一个正整数N，N是叶子节点的个数。(1<=n<=10000)

第2~N+1行包括N个int数据，代表节点权重w[i]。(1<=w[i]<=100000)

输出格式

输出所有节点权重乘长度的总和，即$$\sum_{i=1}^N w[i]\times \textrm{len}[i]$$。

样例输入

Sample1 Input

4
1
2
3
4

Sample2 Input

5
1 
2
3
2
4

样例输出

Sample1 Output

19

Sample1 Explanation

哈夫曼树如下：
      10
     /  \
    6    4
   / \
  3   3  
 / \    
1   2
结果为1*3+2*3+3*2+4*1=19.

Sample2 Output

27

Sample2 Explanation

哈夫曼树如下：

        12
      /    \
     5      7  
    / \    / \
   3   2  4   3
  / \   
 1   2
结果为1*3+2*3+2*2+3*2+4*2=27.

数据范围

输入格式保证合法，输入数据不一定有序。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！