1327_最优二叉树

2022-5-16 18:17| 发布者: Hocassian| 查看: 66| 评论: 0|原作者: 肇庆学院ACM合集

摘要:
C:\Users\Administrator\Downloads\2019-10-12-10-14-2-89503777524199-Problem List-采集的数据-后羿采集器.html

Pro.ID

1327

Title

最优二叉树

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1327

AC

132

Submit

1228

Ratio

10.75%

时间&空间限制

  • Time Limit: 6000/3000 MS (Java/Others)     Memory Limit: 131072/131072 K (Java/Others)
  • 描述

    给出若干个权值,每个权值代表一个字符的出现频率,请为这些字符构造一棵最优二叉树,输出该树的带权路径长度。然后编制一套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
    5 6 2 9 7

    Sample Output

    65
    00
    01
    100
    101
    11

    Author

    样例输入

    5
    5 6 2 9 7

    样例输出

    65
    00
    01
    100
    101
    11

    提示

    作者


    路过

    雷人

    握手

    鲜花

    鸡蛋

    最新评论

    返回顶部