Pro.ID1327 Title最优二叉树 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1327 AC132 Submit1228 Ratio10.75% 时间&空间限制描述给出若干个权值,每个权值代表一个字符的出现频率,请为这些字符构造一棵最优二叉树,输出该树的带权路径长度。然后编制一套Huffman编码。在本题,约定:最优二叉树叶子的路径长度不含叶子节点本身。 在本题,为了确保最优二叉树的唯一性,规定在构造最优二叉树过程中,较小的做左子树,较大一点的做右子树,相等时,先出现的做左子树。并规定编码时采取"左0右1"。 输入测试数据的第一行是一个正整数 N ( 0 < N ≤ 10000 ),表示有N个权值。 接下来一行有N个正整数 Wi ( 0 < Wi < 10000 ),表示各权重值。 输出Description 给出若干个权值,每个权值代表一个字符的出现频率,请为这些字符构造一棵最优二叉树,输出该树的带权路径长度。然后编制一套Huffman编码。在本题,约定:最优二叉树叶子的路径长度不含叶子节点本身。 在本题,为了确保最优二叉树的唯一性,规定在构造最优二叉树过程中,较小的做左子树,较大一点的做右子树,相等时,先出现的做左子树。并规定编码时采取"左0右1"。 Input 测试数据的第一行是一个正整数 N ( 0 < N ≤ 10000 ),表示有N个权值。 接下来一行有N个正整数 Wi ( 0 < Wi < 10000 ),表示各权重值。 Output 首先输出一行:最优二叉树的带权路径长度。 然后输出每行一个Huffman编码,并规定这些Huffman编码的输出顺序是按字典序输出。 Sample Input 5 Sample Output 65 Author 样例输入5 样例输出65 提示作者 |