题目链接：https://vjudge.net/problem/UVA-240

题目大意

　　哈夫曼编码是一种最优编码方法。根据已知源字母表中字符出现的频率，将源字母表中字符编码为目标字母表中字符，最优的意思是编码信息的平均长度最小。在该问题中，你需要将 N 个大写字母（源字母 $S_1 \dots S_N$，频率 $f_1 \dots f_N$）转换成 R 进制数字（目标字母 $T_1 \dots T_R$）。

　　当 R = 2 时，编码过程分几个步骤，每个步骤中，有两个最低频率的源字符 S1、S2，合并 成一个新的“组合字母”，频率为 S1、S2 的频率之和。如果最低频率和次低频率相等，则字母表中最早出现的字母被选中。经过一系列的步骤后，最后只剩两个字母合并，每次合并的字母分配一个目标字符，较低频率的分配 0，另一个分配 1。（如果一个合并中，每个字母有相同的频率，最早出现的分配 0，出于比较的目的，组合字母的值为合并中最早出现的字母的值。）源符号的最终编码由每次形成的目标字符组成。

　　目标字符以相反顺序连接，最终编码序列中第一个字符为分配给组合字母的最后一个目标字符。

　　当 R > 2 时，每一个步骤分配 R 个符号。由于每个步骤将 R 个字母或组合字母合并为一个组合字母，并且最后一次合并必须合并 R 个字母和组合字母，源字母必须包含 k * (R - 1) + R 个字母， k 为整数。由于 N 可能不是很大，因此必须包括适当数量具有零频率的虚拟字母。 这些虚拟的字母不包含在输出中。在进行比较时，虚拟字母晚于字母表中的任何字母。

　　霍夫曼编码的基本过程与 R = 2 情况相同。在每次合并中，将具有最低频率的 R 个字母合并，形成新的组合字母，其频率等于组中包括的字母频率的总和。被合并的字母被分配目标字母符号 0 到 R - 1。

分析

　　先构建哈夫曼树，再生成编码。

　　在处理 R > 2 的情况时，可以按照题目所讲的那样补虚拟字母，也可以先处理掉多余的字母，我采取的是后一种方案。

　　处理完多余字母之后就是中规中矩的哈夫曼问题了。

　　案例见原题。

代码如下

#include
using namespace std;

#define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Rep(i,n) for (int i = 0; i < (n); ++i) #define For(i,s,t) for (int i = (s); i <= (t); ++i) #define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i) #define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)

#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl

#define LOWBIT(x) ((x)&(-x))

#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())

#define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a))
#define msM(a) memset(a,-1,sizeof(a))

#define MP make_pair
#define PB push_back
#define ft first
#define sd second

template
istream &operator>>(istream &in, pair &p) {
in >> p.first >> p.second;
return in;
}

template
istream &operator>>(istream &in, vector &v) {
for (auto &x: v)
in >> x;
return in;
}

template
ostream &operator<<(ostream &out, const std::pair &p) {
out << "[" << p.first << ", " << p.second << "]" << "\n";
return out;
}

inline int gc(){
static const int BUF = 1e7;
static char buf[BUF], *bg = buf + BUF, *ed = bg;

 if(bg == ed) fread(bg = buf, , BUF, stdin);  
 return \*bg++;  

}

inline int ri(){
int x = , f = , c = gc();
for(; c<||c>; f = c=='-'?-:f, c=gc());
for(; c>&&c<; x = x* + c - , c=gc());
return x*f;
}

typedef long long LL;
typedef unsigned long long uLL;
typedef pair< double, double > PDD;
typedef pair< int, int > PII;
typedef pair< int, PII > PIPII;
typedef pair< string, int > PSI;
typedef pair< int, PSI > PIPSI;
typedef set< int > SI;
typedef vector< int > VI;
typedef vector< VI > VVI;
typedef vector< PII > VPII;
typedef map< int, int > MII;
typedef map< int, PII > MIPII;
typedef map< string, int > MSI;
typedef multimap< int, int > MMII;
//typedef unordered_map< int, int > uMII;
typedef pair< LL, LL > PLL;
typedef vector< LL > VL;
typedef vector< VL > VVL;
typedef priority_queue< int > PQIMax;
typedef priority_queue< int, VI, greater< int > > PQIMin;
const double EPS = 1e-;
const LL inf = 0x7fffffff;
const LL infLL = 0x7fffffffffffffffLL;
const LL mod = 1e9 + ;
const int maxN = 1e4 + ;
const LL ONE = ;
const LL evenBits = 0xaaaaaaaaaaaaaaaa;
const LL oddBits = 0x5555555555555555;

template
inline string toString(T x) {
ostringstream sout;
sout << x;
return sout.str();
}

// R: 基數
// N: 字母數量
// T: 案例標號
int R, N, T;
int freq[], freqSum;
string codes[];

// expSum: 期望和
LL expSum;
double avglen;

struct Node{
LL timestamp = infLL;
int letter = ;
int weight = ;
vector< Node > nexts;

 bool operator< (const Node &x) const {  
     if(weight == x.weight) return timestamp > x.timestamp;  
     return weight > x.weight;  
 }  

};
Node root;

void buildHuffmanTree() {
priority_queue< Node > minH;

 Rep(i, N) {  
     Node t;  
     t.letter = i;  
     t.weight = freq\[i\];  
     t.timestamp = i;  
     minH.push(t);  
 }

 // 題目中說要補問號占位符，我這裏就不補了，直接把需要補充的節點合成一個代表節點  
 int r = (N - ) % (R - );  
 if(r) r += ;

 Node tmpR;  
 Rep(i, r) {  
     Node tmp = minH.top(); minH.pop();

     tmpR.nexts.PB(tmp);  
     tmpR.weight += tmp.weight;  
     // 代表節點的時間戳由集合中最早的節點決定  
     tmpR.timestamp = min(tmpR.timestamp, tmp.timestamp);  
 }  
 if(tmpR.weight) minH.push(tmpR);

 // 正式建树  
 while(minH.size() >= R) {  
     Node t;  
     Rep(i, R) {  
         Node tmp = minH.top(); minH.pop();

         t.nexts.PB(tmp);  
         t.weight += tmp.weight;  
         // 代表節點的時間戳由集合中最早的節點決定  
         t.timestamp = min(t.timestamp, tmp.timestamp);  
     }  
     minH.push(t);  
 } 

 //assert(minH.size() == 1);  
 root = minH.top();  

}

void dfs(Node &rt, string ret, int deep) {
if(!rt.nexts.size()) {
codes[rt.letter] = ret;
expSum += freq[rt.letter] * deep;
return;
}

 Rep(i, rt.nexts.size()) {  
     //assert((i + R - rt.nexts.size()) / 10 == 0);  
     dfs(rt.nexts\[i\], ret + toString(i + R - rt.nexts.size()), deep + );  
 }  

}

void generateCode() {
expSum = ;

 dfs(root, "", );

 avglen = 1.0 \* expSum / freqSum;  

}

int main(){
//freopen("MyOutput.txt","w",stdout);
//freopen("input.txt","r",stdin);
//INIT();
while(cin >> R) {
if(!R) break;
cin >> N;
freqSum = ;
Rep(i, N) {
cin >> freq[i];
freqSum += freq[i];
}

     buildHuffmanTree();  
     generateCode();

     printf("Set %d; average length %.2f\\n", ++T, avglen);  
     Rep(i, N) printf("    %c: %s\\n", i + 'A', codes\[i\].c\_str());  
     printf("\\n");  
 }  
 return ;  

}