题意
哈夫曼编码是一种最优编码方法。根据已知源字母表中字符出现的频率，将源字母表中字符编码为目标字母表中字符，最优的意思是编码信息的平均长度最小。在该问题中，你需要将 \(N\) 个大写字母（源字母 \(S_1 …S_N\)，频率 \(f_1…f_N\)）转换成 \(R\) 进制数字（目标字母 \(T_1 …T_R\)）。
当 \(R=2\) 时，编码过程分几个步骤，每个步骤中，有两个最低频率的源字符 \(S_1, S_2\) ，合并成一个新的“组合字母”，频率为 \(R_1 + R_2\)。如果最低频率和次低频率相等，则字母表中最早出现的字母被选中。经过一系列的步骤后，最后只剩两个字母合并，每次合并的字母分配一个目标字符，较低频率的分配 \(0\)，另一个分配 \(1\)。（如果一个合并中，每个字母有相同的频率，最早出现的分配 \(0\)，出于比较的目的，组合字母的值为合并中最早出现的字母的值。）源符号的最终编码由每次形成的目标字符组成。
目标字符以相反顺序连接，最终编码序列中第一个字符为分配给组合字母的最后一个目标字符。
当 $ R>2 $ 时，每一个步骤分配 $ R $ 个字母。由于每个步骤将 $ R $ 个字母或组合字母合并为一个组合字母，并且最后一次合并必须合并 $ R $ 个字母和组合字母，源字母必须包含 $ k \times (R-1)+R $ 个字母， \(k\) 为整数。由于 \(N\) 可能不是很大，因此必须包括适当数量具有零频率的虚拟字母。
这些虚拟的字母不包含在输出中。在进行比较时，虚拟字母晚于字母表中的任何字母。
霍夫曼编码的基本过程与 $ R = 2 $ 情况相同。在每次合并中，将具有最低频率的 $ R $ 个字母合并，形成新的组合字母，其频率等于组中包括的字母频率的总和。被合并的字母被分配目标字母符号 $ 0 $ 到 $ R-1 $。\(0\) 被分配给具有最低频率的组合中的字母，\(1\) 被分配给下一个最低频率，等等。 如果组中的几个字母具有相同的频率，则字母表中最早的字母被分配较小的目标符号，依此类推。
输入格式
输入将包含一个或多个数据集，每行一个。 每个数据集都包含一个整数值 \(R\)（$ 2 \leq R \leq 10 $），整数值 \(N\)（$ 2 \leq N \leq 26 $）和整数频率 $ f_1 …f_N $ ，每个都在 \([1, 999]\) 之间。
整个输入的数据结束是 \(R\) 为 \(0\), 它不被认为是单独的数据集。
输出格式
对于每个数据集，在一行上显示其编号（编号从 \(1\) 开始按顺序排列）和平均目标符号长度（四舍五入到小数点后两位）。 然后显示 \(N\) 个源字母和相应的霍夫曼代码，每行一个字母和代码。在每个测试用例后打印一个空行。
\(Code\)
可变基哈夫曼编码（这里的基指每位编码可选择的数字，$ 0,1,2 … R-1 $），普通的哈夫曼编码为 \(R=2\)，也就是将字符变成二进制编码，而这里是变成R进制编码。只需按题目中说的补充一些虚拟节点，使得节点个数为 $ k \times (R-1)+R$，其余按 \(R=2\) 的时候一样找最小的 \(R\) 个数字合并，一步步处理。
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
using namespace std;
typedef long long ll;
const int maxn=105;
struct node{
int w,va,id;
bool operator <(const node &b)const{
if(w==b.w) return va>b.va;
return w>b.w;
}
};
int R,N,n,a[maxn],f[maxn],code[maxn];
int sum1,sum2;
priority_queue<node> q;
int main (){
int cnt=1;
while(scanf("%d",&R) && R!=0){
//左闭右开区间，赋值为0
fill(a,a+maxn,0);
fill(f,f+maxn,0);
fill(code,code+maxn,0);
sum1=sum2=0;
while(!q.empty())q.pop();
//输入,sum1统计总字符数
scanf("%d",&N);
for(int i=1;i<=N;i++){
scanf("%d",&a[i]);
sum1+=a[i];
}
//添加虚拟节点
n=N;
while(n<R || (n-R)%(R-1)!=0) n++;
for(int i=1;i<=n;i++)q.push(node{a[i],i,i});
//构建哈夫曼树
while(q.size()>1){
int total=0,minva=n;
n++;
for(int i=0;i<R;i++){
total+=q.top().w;//统计字符转化成哈夫曼编码后的长度和
minva=min(minva,q.top().va);//当权值相等时根据它们子节点的最先出现顺序合并
code[q.top().id]=i;//记录编码
f[q.top().id]=n;//记录父亲节点
q.pop();
}
q.push(node{total,minva,n});
sum2+=total;//统计字符转化成哈夫曼编码后的总长度和
}
printf("Set %d; average length %.2f\n",cnt++,1.0*sum2/sum1);
//从叶子节点往上走，求哈夫曼编码
for(int i=1;i<=N;i++){
int x=i;
string s="";
while(f[x]!=0){
s+=char(code[x]+'0');
x=f[x];
}
reverse(s.begin(),s.end());//翻转字符串
cout<<" "<<char('A'+i-1)<<": "<<s<<endl;
}
cout<<endl;
}
return 0;
}
原文地址：http://www.cnblogs.com/mrCrazyWolf/p/16928426.html
