问题 3834 --Haffman编码

3834: Haffman编码

时间限制: 1 Sec  内存限制: 128 MB
提交: 7  解决: 3
[提交][状态][讨论版][数据上传:][下载FPS1元][添加到购物车][下载测试数据1元][20kb]

题目描述

哈弗曼编码大家一定很熟悉吧(不熟悉也没关系,自己查去。。。)。现在给你一串字符以及它们所对应的权值,让你构造哈弗曼树,从而确定每个字符的哈弗曼编码。当然,这里有一些小规定:

1.规定哈弗曼树的左子树编码为0,右子树编码为1;

2.若两个字符权值相同,则ASCII码值小的字符为左孩子,大的为右孩子;

3.创建的新节点所代表的字符与它的做孩子的字符相同;

4.所有字符为ASCII码表上32-96之间的字符(即“ ”到“`”之间的字符)。

输入

输入包含多组数据(不超过100组)
每组数据第一行一个整数n,表示字符个数。接下来n行,每行有一个字符ch和一个整数weight,表示字符ch所对应的权值,中间用空格隔开。
输入数据保证每组测试数据的字符不会重复。

输出

对于每组测试数据,按照输入顺序输出相应的字符以及它们的哈弗曼编码结果,具体格式见样例。

样例输入

3
a 10
b 5
c 8
4
a 1
b 1
c 1
d 1

样例输出

a:0
b:10
c:11
a:00
b:01
c:10
d:11

提示

来源

[提交][状态]