Problem1545--哈夫曼树

1545: 哈夫曼树

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 498  Solved: 154
[Submit] [Status] [Web Board] [Creator:]

Description

有一棵二叉树有n个叶子结点,每个叶子结点有一个权值,求最小带权路径长度。

Input

多组输入。
第一行输入叶子结点数n(1<=n<=1000)。
接下来一行输入n个正整数(不超过1000),代表每个叶子结点的权值。

Output

输出由这n个叶子结点构成的二叉树的最小带权路径长度。

Sample Input

3
1 2 3

Sample Output

9

HINT

对于测试用例,可以构建一棵这样的树:

Source/Category