Problem Description
Javac++ 一天在看计算机的书籍的时候，看到了一个有趣的东西！每一串字符都可以被编码成一些数字来储存信息，但是不同的编码方式得到的储存空间是不一样的！并且当储存空间大于一定的值的时候是不安全的！所以Javac++ 就想是否有一种方式是可以得到字符编码最小的空间值！显然这是可以的，因为书上有这一块内容--哈夫曼编码(Huffman Coding)；一个字母的权值等于该字母在字符串中出现的频率。所以Javac++ 想让你帮忙，给你安全数值和一串字符串，并让你判断这个字符串是否是安全的？
Input
输入有多组case，首先是一个数字n表示有n组数据，然后每一组数据是有一个数值m(integer)，和一串字符串没有空格只有包含小写字母组成！
Output
如果字符串的编码值小于等于给定的值则输出yes，否则输出no。
Sample Input
2
12
helloworld
66
ithinkyoucandoit
12
helloworld
66
ithinkyoucandoit
Sample Output
no
yes
yes
一道简单的哈弗曼树，一开始没看懂题意，经过别人告诉我题意，原来只是一道这么简单的哈夫曼树，题目是要求除了叶子节点外的所有节点权值之和，正好数据结构刚刚学了哈夫曼树，趁热打铁。
要注意的是，如果在字符只有一种的情况下，哈夫曼树是建不起来的，要特殊处理
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std; const int L = 1000000+10;
const int inf = 1<<30;
char str[L];
struct kode
{
int num;
char c;
} b[L<<2]; struct node
{
int wei,parent,lson,rson,cover;
char data;
} a[L<<2]; int main()
{
int i,j,sum,t,len,lb;
char ch;
scanf("%d",&t);
while(t--)
{
scanf("%d%s",&sum,str);
len = strlen(str);
sort(str,str+len);
for(i = 0; i<len<<2; i++)
{
a[i].cover = a[i].lson = a[i].rson = a[i].parent = a[i].wei = b[i].num = 0;
a[i].data = b[i].c = '\0';
}
lb = 0;
b[lb].num = 1;
b[lb].c = ch = str[0];
for(i = 1; i<len; i++)
{
if(str[i] == ch)
b[lb].num++;
else
{
lb++;
ch = str[i];
b[lb].c = ch;
b[lb].num = 1;
}
}
if(lb == 0)//只有一种类型的字符，直接比较
{
if(b[lb].num<=sum)
printf("yes\n");
else
printf("no\n");
continue;
}
lb++;
int m = lb*2-1;
for(i = 0; i<lb; i++)
{
a[i].data = b[i].c;
a[i].wei = b[i].num;
}
for(i = 0; i<lb; i++)//建立哈夫曼树
{
int m1 = inf,m2 = inf;
int x = 0,y = 0;
for(j = 0; j<lb+i; j++)
{
if(a[j].wei<m1 && !a[j].cover)
{
m2 = m1;
m1 = a[j].wei;
y = x;
x = j;
}
else if(a[j].wei<m2 && !a[j].cover)
{
m2 = a[j].wei;
y = j;
}
}
a[x].parent = lb+i;
a[y].parent = lb+i;
a[lb+i].lson = x;
a[lb+i].rson = y;
a[lb+i].wei = a[x].wei+a[y].wei;
a[x].cover = a[y].cover = 1;
}
int ans = 0;
for(i = lb; i<2*lb-1; i++)//求除了叶子节点外其他所有节点的权值和
ans+=a[i].wei;
if(ans<=sum)
printf("yes\n");
else
printf("no\n");
} return 0;
}