程序设计在线评测(Online Judge)

从http://acm.hnust.edu.cn/web登录可查看比赛的OI排名分。

问题 1071. -- 赫夫曼编码

1071: 赫夫曼编码

时间限制: 1 Sec  内存限制: 128 MB
提交: 552  解决: 146
[提交][状态][讨论版]

题目描述

赫夫曼编码能够产生最短的报文。以报文“ABCDABCDABCABDABAA”为例,A编为0B对应10C对应110D对应111,整体的报文长度为35位二进制。相比于定长的ASCII码,压缩比达到了18*8/35=4.1

输入

输入有一系列的字符串组成,每个字符串占据一行。字符串仅包含大写字母和下划线。字符串“END” 表示处理结束,不应对其处理。

输出

对每一个字符串,输出其ASCII编码的比特位长度,赫夫曼编码的比特位长度,以及二者之比,精确到小数点后一位。

样例输入

ABCDABCDABCABDABAA
AAAAAAAAAAAAAAAAAA
END

样例输出

144 35 4.1
144 18 8.0

提示

 要求书中算法取权值最小的部分使用堆来实现

来源

[提交][状态][讨论版]