C1096 - 哈夫曼编码与解码
题目描述
小明刚学过哈夫曼树和哈夫曼编码的相关知识，现在老师想要考他一考，让他写个程序来进行哈夫曼的编码与解码
输入格式
第1行，1个正整数n，代表接下来需要进行哈夫曼编码的字符个数
接下来n行，每行格式：
字母 空格 字母出现的频率
接下来1行，一串由这些字母组成的字符串s1，待编码的字符串（不包含空格）
接下来1行，一串哈夫曼编码的二进制内容s2，待解码的哈夫曼编码（不包含空格）
输出格式
第1行，字符串s1对应的二进制哈夫曼编码（哈夫曼编码结果）
第2行，哈夫曼编码s2对应的原始字符串（哈夫曼解码结果）
输入输出样例
| 输入样例 | 输出样例 |
|---|---|
| 6 a 5 b 9 c 12 d 13 e 16 f 45 abcdefg 000100101111110011011101 |
110011011001011110 fffcdeabb |
输入输出样例说明
上面的样例说明对应的哈夫曼树为：
数据范围与提示
说明： 由于哈夫曼编码的不唯一性，这里约定在构建哈夫曼树的时候，将权值小的叶子节点作为左子树节点，同时题目提供的数据保证按照约定构建的每个字符的哈夫曼编码是确定唯一的
对于100%的数据满足：$2 \le n \le 10$，s1的长度 <= 100，s2的长度 <= 400，需要编码的字符为英文大小写字母
测试点数目
共5个测试点，每个测试点20分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式
1. 标准输入输出模式：
直接从标准输入和标准输出读写数据，不需要使用freopen进行文件输入输出重定向
2. 文件输入输出模式（国内信奥赛输入输出模式）:
从文件中读写数据，需要使用freopen进行输入输出重定向
本题输入文件名为：C1096.in，输出文件名为：C1096.out