1 #include <iostream>
  2 using namespace std;
  3 #define MAXNODE 10010
  4 struct HTNode{
  5     char data;        //节点值
  6     double weight;    //权重
  7     int parent;        //双亲节点 
  8     int lchild;        //左孩子节点
  9     int rchild;        //右孩子节点 
 10 }ht[2*MAXNODE-1];
 11 struct HCode{
 12     char cd[MAXNODE];
 13     int start;
 14 }hcd[MAXNODE];
 15 char str[MAXNODE];
 16 void CreateHT(HTNode ht[],int n)
 17 {
 18     int i,j,k,lnode,rnode;
 19     double min1,min2;
 20     for(i=0;i<2*n-1;i++)    //所有节点的相关域置初值-1 
 21         ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
 22     for(i=n;i<2*n-1;i++){    //构造哈夫曼树 
 23         min1 = min2 = 9999999;    //lnode和rnode为权重最小的两个节点位置
 24         lnode = rnode =-1;
 25         for(k=0;k<=i-1;k++)
 26             if(ht[k].parent == -1){
 27                 if(ht[k].weight<min1){
 28                     min2 = min1;rnode = lnode;
 29                     min1 = ht[k].weight;lnode = k;
 30                 }
 31                 else if(ht[k].weight<min2){
 32                     min2 = ht[k].weight;rnode = k;
 33                 }
 34             } 
 35         ht[i].weight = ht[lnode].weight + ht[rnode].weight;
 36         ht[i].lchild = lnode;ht[i].rchild = rnode;    //ht[i]作为双亲节点
 37         ht[lnode].parent = i;ht[rnode].parent = i; 
 38     }
 39 }
 40 void CreateHCode(HTNode ht[],HCode hcd[],int n)
 41 {
 42     int i,f,c;
 43     HCode hc;    
 44     for(i=0;i<n;i++){    //根据哈夫曼树求哈夫曼编码      
 45         hc.start = n;c=i;
 46         f = ht[i].parent;
 47         while(f!=-1){
 48             if(ht[f].lchild == c)
 49                 hc.cd[hc.start--] = ‘0‘;
 50             else
 51                 hc.cd[hc.start--] = ‘1‘;
 52             c = f;f=ht[f].parent;
 53         }
 54         hc.start++;
 55         hcd[i]=hc;
 56     }
 57 }
 58 int main()
 59 {
 60     int n;
 61     cin>>n;
 62     while(n--){
 63         int m;
 64         cin>>m;
 65         cin>>str;
 66         int len = 0;
 67         for(int i=0;str[i];i++){    //初始化ht[]哈夫曼树的叶子节点和权值 
 68             //ht[]有无存储str[i]
 69             int j;
 70             for(j=0;j<len;j++)
 71                 if(str[i]==ht[j].data)
 72                     break;
 73             if(j<len) continue;    //已经存储了，退出本次循环 
 74             int count = 0;
 75             for(j=0;str[j];j++){    //没存储，给ht[len]计数 
 76                 if(str[i]==str[j])
 77                     count++;
 78             }
 79             ht[len].data = str[i];
 80             ht[len++].weight = count;
 81         }
 82         //len--;
 83         CreateHT(ht,len);    //创建哈夫曼树 
 84         CreateHCode(ht,hcd,len);    //根据哈夫曼树求哈夫曼编码 
 85         if(len==1){    //只有一种字符的情况下，哈夫曼树是构造不起来的，特殊处理（直接进行比较） 
 86             if(ht[0].weight<=m)
 87                 cout<<"yes"<<endl;
 88             else
 89                 cout<<"no"<<endl;
 90             continue;
 91         }
 92         int wpl = 0;
 93         for(int i=0;i<len;i++){
 94             wpl += (len-hcd[i].start+1)*ht[i].weight;
 95         }
 96         //cout<<wpl<<endl;
 97         if(wpl<=m)
 98             cout<<"yes"<<endl;
 99         else 
100             cout<<"no"<<endl;
101     }
102     return 0;
103 }