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
#include
#include
#include
#include
#pragma warning(disable:4996)
#define MAXLEN 110
using namespace std;
struct HuffmanTree {
int w;
int left, right, parent;
HuffmanTree()
{
w = left = right = parent = 0;
}
};
int w[MAXLEN];//权值
string huffmanCode[MAXLEN];//哈夫曼编码
HuffmanTree ht[MAXLEN*2];
map Hash;
int totalLength;
//初始化
void init()
{
for (int i = 1; i <= MAXLEN; ++i)
{
ht[i].left = ht[i].right = ht[i].parent = 0;
}
fill(w, w + MAXLEN, 0);
Hash.clear();
totalLength = 0;
}
//从哈夫曼树中选出没有父节点，权值最小的两个节点的下标
void select(HuffmanTree *ht,int n,int &s1,int &s2)
{
int min = INT_MAX;
int i;
for (i = 1; i <= n; ++i)
{
if (ht[i].parent == 0 && ht[i].w < min)
{
min = ht[i].w;
s1 = i;
}
}
min = INT_MAX;
for (i = 1; i <= n; ++i)
{
if (ht[i].parent == 0 && i!= s1 && ht[i].w < min)
{
min = ht[i].w;
s2 = i;
}
}
if (s1 > s2)
swap(s1, s2);
}
//建立哈夫曼树并编码
void HuffmanCoding(HuffmanTree * ht,string *hfCode,int *weight,int n)
{
if (n <= 1)
return;
//ht = new HuffmanTree[n * 2];//哈夫曼树节点个数为2*n-1个，这里数组0不用，所以分配2*n个
//为叶子节点赋上权值
int i,s1,s2;
for (i = 1; i <= n; ++i)
ht[i].w = weight[i];
for (i = n + 1; i <= 2 * n - 1; ++i)
{
select(ht, i - 1, s1, s2);
ht[i].w = ht[s1].w + ht[s2].w;
ht[s1].parent = ht[s2].parent = i;
ht[i].left = s1;
ht[i].right = s2;
}
//从每个叶子节点向上查找，直到找到根节点，
//如果当前节点是父节点的左孩子编码为0，否则为1
int c, p;
for (i = 1; i <= n; ++i)
{
c = i;
string temp;
while (ht[c].parent != 0)
{
p = ht[c].parent;
if (ht[p].left == c)
temp.insert(temp.begin(), '0');
else
temp.insert(temp.begin(), '1');
c = p;
}
hfCode[i] = temp;
totalLength += temp.size();
}
}
int setWeight(string &str)
{
char ch;
for (int i = 0; i < str.size(); ++i)
{
ch = str[i];
if (Hash.find(ch) == Hash.end())
{
Hash[ch] = 1;
}
else
{
++Hash[ch];
}
}
int index = 0;
for (auto it = Hash.begin(); it != Hash.end(); ++it)
{
w[++index] = it->second;
}
return index;//返回节点个数
}
int main()
{
int n,m,nodeNum;
string str;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
init();
cin >> m;
cin >> str;
nodeNum = setWeight(str);
HuffmanCoding(ht, huffmanCode, w, nodeNum);//哈夫曼编码
if (totalLength <= m)
cout << "yes" << endl;
else
cout << "no" << endl;
}
system("pause");
return 0;
}