1926: 可变基数哈夫曼编码（洛谷UVA240）
时间限制: 1 Sec 内存限制: 128 MB提交: 6 解决: 3
[提交] [状态] [讨论版] [命题人:]
题目描述
哈夫曼编码是一种最优编码方法。根据已知源字母表中字符出现的频率，将源字母表中字符编码为目标字母表中字符，最优的意思是编码信息的平均长度最小。在该问题中，你需要将 N 个大写字母（源字母 S 1 …S N ，频率 f 1 …f N ）转换成 R 进制数字（目标字母 T 1 …T R ）。
当 R=2 时，编码过程分几个步骤，每个步骤中，有两个最低频率的源字符 S 1 、 S 2 ，合并成一个新的“组合字母”，频率为 S 1 、 S 2 的频率之和。如果最低频率和次低频率相等，则字母表中最早出现的字母被选中。经过一系列的步骤后，最后只剩两个字母合并，每次合并的字母分配一个目标字符，较低频率的分配 0，另一个分配 1。（如果一个合并中，每个字母有相同的频率，最早出现的分配 0，出于比较的目的，组合字母的值为合并中最早出现的字母的值。）源符号的最终编码由每次形成的目标字符组成。
目标字符以相反顺序连接，最终编码序列中第一个字符为分配给组合字母的最后一个目标字符。
下面的两个插图展示了 R = 2 的过程。
当 R>2 时，每一个步骤分配 R 个符号。由于每个步骤将 R 个字母或组合字母合并为一个组合字母，并且最后一次合并必须合并 R 个字母和组合字母，源字母必须包含 k*(R-1)+R个字母， k 为整数。由于 N 可能不是很大，因此必须包括适当数量具有零频率的虚拟字母。
这些虚拟的字母不包含在输出中。在进行比较时，虚拟字母晚于字母表中的任何字母。
霍夫曼编码的基本过程与 R = 2 情况相同。在每次合并中，将具有最低频率的 R 个字母合并，形成新的组合字母，其频率等于组中包括的字母频率的总和。被合并的字母被分配目标字母符号 0 到 R-1。0 被分配给具有最低频率的组合中的字母，1 被分配给下一个最低频率，等等。 如果组中的几个字母具有相同的频率，则字母表中最早的字母被分配较小的目标符号，依此类推。
下图说明了 R = 3 的过程：
当 R=2 时，编码过程分几个步骤，每个步骤中，有两个最低频率的源字符 S 1 、 S 2 ，合并成一个新的“组合字母”，频率为 S 1 、 S 2 的频率之和。如果最低频率和次低频率相等，则字母表中最早出现的字母被选中。经过一系列的步骤后，最后只剩两个字母合并，每次合并的字母分配一个目标字符，较低频率的分配 0，另一个分配 1。（如果一个合并中，每个字母有相同的频率，最早出现的分配 0，出于比较的目的，组合字母的值为合并中最早出现的字母的值。）源符号的最终编码由每次形成的目标字符组成。
目标字符以相反顺序连接，最终编码序列中第一个字符为分配给组合字母的最后一个目标字符。
下面的两个插图展示了 R = 2 的过程。
当 R>2 时，每一个步骤分配 R 个符号。由于每个步骤将 R 个字母或组合字母合并为一个组合字母，并且最后一次合并必须合并 R 个字母和组合字母，源字母必须包含 k*(R-1)+R个字母， k 为整数。由于 N 可能不是很大，因此必须包括适当数量具有零频率的虚拟字母。
这些虚拟的字母不包含在输出中。在进行比较时，虚拟字母晚于字母表中的任何字母。
霍夫曼编码的基本过程与 R = 2 情况相同。在每次合并中，将具有最低频率的 R 个字母合并，形成新的组合字母，其频率等于组中包括的字母频率的总和。被合并的字母被分配目标字母符号 0 到 R-1。0 被分配给具有最低频率的组合中的字母，1 被分配给下一个最低频率，等等。 如果组中的几个字母具有相同的频率，则字母表中最早的字母被分配较小的目标符号，依此类推。
下图说明了 R = 3 的过程：
输入
输入将包含一个或多个数据集，每行一个。 每个数据集都包含一个整数值 R（2≤R≤10）,整数值 N（2≤R≤26）和整数频率 f 1 …f N ，每个都在 1 到 999 之间。整个输入的数据结束是 R 为 0; 它不被认为是单独的数据集。
输出
对于每个数据集，在一行上显示其编号（编号从 1 开始按顺序排列）和平均目标符号长度（四舍五入到小数点后两位）。 然后显示 N 个源字母和相应的霍夫曼代码，每行一个字母和代码。在每个测试用例后打印一个空行。
样例输入 Copy
2 5 5 10 20 25 40
2 5 4 2 2 1 1
3 7 20 5 8 5 12 6 9
4 6 10 23 18 25 9 12
0
样例输出 Copy
Set 1; average length 2.10
A: 1100
B: 1101
C: 111
D: 10
E: 0
Set 2; average length 2.20
A: 11
B: 00
C: 01
D: 100
E: 101
Set 3; average length 1.69
A: 1
B: 00
C: 20
D: 01
E: 22
F: 02
G: 21
Set 4; average length 1.32
A: 32
B: 1
C: 0
D: 2
E: 31
F: 33