#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;
}