http://acm.hdu.edu.cn/showproblem.php?pid=2527
建哈夫曼树，哈夫曼编码，求wpl值。
Safe Or Unsafe
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1511 Accepted Submission(s): 594
Problem Description
Javac++ 一天在看计算机的书籍的时候，看到了一个有趣的东西！每一串字符都可以被编码成一些数字来储存信息，但是不同的编码方式得到的储存空间是不一样的！并且当储存空间大于一定的值的时候是不安全的！所以Javac++ 就想是否有一种方式是可以得到字符编码最小的空间值！显然这是可以的，因为书上有这一块内容--哈夫曼编码(Huffman Coding)；一个字母的权值等于该字母在字符串中出现的频率。所以Javac++ 想让你帮忙，给你安全数值和一串字符串，并让你判断这个字符串是否是安全的？
Input
输入有多组case，首先是一个数字n表示有n组数据，然后每一组数据是有一个数值m(integer)，和一串字符串没有空格只有包含小写字母组成！
Output
如果字符串的编码值小于等于给定的值则输出yes，否则输出no。
Sample Input
2
12
helloworld
66
ithinkyoucandoit
Sample Output
no
yes
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct node
{
char ch;//节点值
int weight;//权重
int parent;//双亲节点
int lchild,rchild;//孩子节点
}ht[];
struct Hcode
{
char cd[];//存入01编码的字符串。
int start;//长度的开始。
}hcd[];
void creat(node ht[],char *c,int *w,int n)//建哈夫曼树。
{
int i,s1,s2,k,min1,min2;
for(i=;i<=n;i++)//初始化叶子节点
{
ht[i].ch=c[i-];//字符。
ht[i].weight=w[i-];//权值
ht[i].parent=ht[i].lchild=ht[i].rchild=;//开始为0.
}
for(;i<*n;i++)//树的节点一共为2*n-1个。
{
ht[i].parent=;
ht[i].lchild=;
ht[i].rchild=;
}
for(i=n+;i<*n;i++)
{
min1 = min2 = ;
for(k=;k<=i-;k++)//求权值最小的2个权值。
if(ht[k].parent == )
{
if(ht[k].weight<min1)
{
min2 = min1;
s2= s1;
min1= ht[k].weight;
s1= k;
}
else if(ht[k].weight<min2)
{
min2 = ht[k].weight;
s2 = k;
}
} ht[s1].parent=i;//建立节点。
ht[s2].parent=i;
ht[i].lchild=s1;
ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight; } }
void creatHcode(node ht[],Hcode hcd[],int n)//哈夫曼编码。
{
int i,f,c;
Hcode hc;
for(i=;i<=n;i++)
{
hc.start=n;
c=i;
f=ht[i].parent;
while(f!=)
{
if(ht[f].lchild==c)
hc.cd[hc.start--]='';
else
hc.cd[hc.start--]='';
c=f;
f=ht[f].parent;
}
hc.start++;
hcd[i]=hc;
}
}
int main()
{
int T,m,i,r,j;
int w[];
char str[],c[];
scanf("%d",&T);
while(T--)
{
memset(w,,sizeof(w));
scanf("%d",&m);
getchar();
scanf("%s",str);
int len=strlen(str);
r=;
c[r++]=str[];
w[]=;
for(i=;i<len;i++)
{
for(j=;j<r;j++)
{
if(c[j]==str[i])
{
w[j]=w[j]+;
break;
}
}
if(j==r)
{ w[r]=;
c[r++]=str[i];
}
}
c[r]='\0';
if(r==)
{
if(w[]<=m)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
continue;
}
creat(ht,c,w,r);
creatHcode(ht,hcd,r);
int wpl=;
for(i=;i<=r;i++)
{
wpl+=(r-hcd[i].start+)*ht[i].weight; }
if(wpl<=m)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
return ;
}