| 题目名称 | 3192. 哈夫曼编码 |
|---|---|
| 输入输出 | hfmcode.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 syzhaoss
于2019-06-26加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：10， 提交：36， 通过率：27.78% | ||||
 1020 |
100 | 0.000 s | 0.00 MiB | C++ |
 lihaoze |
100 | 0.000 s | 0.00 MiB | C++ |
|
lihaoze |
100 | 0.000 s | 0.00 MiB | C++ |
|
dew52 |
100 | 0.000 s | 0.00 MiB | C++ |
|
dew52 |
100 | 0.000 s | 0.00 MiB | C++ |
|
喵喵喵 |
100 | 0.000 s | 0.00 MiB | C++ |
 Hzoi_Mafia |
100 | 0.000 s | 0.00 MiB | C++ |
|
什么都想学什么都学了一点的晓无痕 |
100 | 0.000 s | 0.61 MiB | C++ |
|
syzhaoss |
100 | 0.006 s | 13.67 MiB | C++ |
 cb |
100 | 0.008 s | 13.70 MiB | C++ |
| 关于 哈夫曼编码 的近10条评论(全部评论) |
|---|
【题目描述】
计算机网络传输中需将传送的文字转换成由二进制的字符组成的字符串。例如，假设需传送的字串为”ABACCDA”，它只有四种字符，只需两个字符的串便可分辨。假设A、B、C、D的编码分别为00、0l、10和11，则上述七个字符的字串便为”00010010101100”，总长14位，对方接收时，可按二位一分进行译码。
在传送时，希望编码总长尽可能地短。如果对每个字符设计长度不等的编码，且让字串中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。
如果设计A、B、C、D的编码分别为0,01,1和10，则上述七个字符的字串可转换成总长为9的字符。但这种编码会导致无法解码，因为任一个字符的编码都不能是另一个字符的编码的前缀。
现在给你一篇待传送的文字，请你编程为每一个字符设计编码，使得编码总长最短。
【输入格式】
输入文件有一行，全部由大写英文字母组成，字符个数不超过10000个。
【输出格式】
输出文件只有一个整数，即编码总长。
【样例输入】
ABACCDA
【样例输出】
13