j. 转换哈夫曼编码
转换哈夫曼编码
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
静态哈夫曼编码是一种主要用于文本压缩的编码算法。
给定一个由 N 个不同字符组成的特定长度的文本，算法选择 N 个编码，每个不同的字符都对应一个编码。使用这些编码压缩文本，当选择编码算法构建一个具有 N 个叶子的二叉树时，对于 N ≥2，树的构建流程如下。
（1）对文本中的每个不同字符，都构建一个仅包含单个节点的树，其权值为该字符在文本中的出现次数。
（2）构建一个包含上述N 棵树的集合S 。
（3）当S 包含多于一棵树时：
- ①选择最小的权值 t1 ∈S ，并将其从S 中删除；
- ②选择最小的权值 t2 ∈S ，并将其从S 中删除；
- ③构建一棵新树 t ，t1 为其左子树，t2 为其右子树，t 的权值为t1、t2值之和；
- ④将 t 加入S 集合。
（4）返回保留在 S 中的唯一一棵树。
对于文本“abracadabra”，由上述过程生成的树，可以像下面左图，其中每个叶子节点内都是该字符在文本中出现的次数（权值）。请注意获得的树不是唯一的，也可以像下面右图或其他，因为可能包含几个权值最小的树。
对文本中的每个不同字符，其编码都取决于最终树中从根到对应字符的叶子之间的路径，编码的长度是这条路径中的边数。假设该算法构建的是左侧的树，“r”的代码长度为3，“d”的代码长度为4。根据算法选择的N 个代码的长度，找所有字符总数的最小值。
输入格式
输入包含多个测试用例，每个测试用例的格式如下：
第1行都包含一个整数，表示在文本中出现的不同字符数。
第2行包含N个整数，表示由哈夫曼算法生成的不同字符的编码长度。假设至少存在一棵由上述算法构建的树，那么可以生成具有给定长度的编码。
输出个数
对每个测试用例都输出一行，表示所有字符总数的最小值。
样例
2
1 1
4
2 2 2 2
10
8 2 4 7 5 1 6 9 3 9
2
4
89
数据范围
来源
UVA12676