1 //0MS    376K    1953 B    G++
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<queue>
 5 using namespace std;
 6 typedef struct Huffman{
 7     int deep;
 8     int fred;
 9     Huffman *left,*right;
10     friend bool operator <(Huffman a,Huffman b){
11         return a.fred>b.fred;
12     }
13 }Huffman;
14 Huffman trie[10005];
15 Huffman *root;
16 int len,id,sum;
17 int cnt;
18 priority_queue<Huffman>Q;
19 
20 void huffman()
21 {
22     sum=0;
23     root=(Huffman*)malloc(sizeof(Huffman));
24     for(int i=0;i<id;i++) 
25         Q.push(trie[i]);
26     while(Q.size()>1){
27         Huffman *h1=(Huffman*)malloc(sizeof(Huffman));
28         *h1=Q.top();
29         Q.pop();
30         Huffman *h2=(Huffman*)malloc(sizeof(Huffman));
31         *h2=Q.top();
32         Q.pop();
33         
34         Huffman h3;
35         h3.left=h1;
36         h3.right=h2;
37         h3.fred=h1->fred+h2->fred;
38         Q.push(h3);
39     }
40     *root=Q.top();
41     Q.pop();
42     root->deep=0;
43     
44     queue<Huffman>q;
45     q.push(*root);
46     while(!q.empty()){
47         Huffman ht=q.front();
48         q.pop();
49         if(ht.left!=NULL){
50             ht.left->deep=ht.deep+1;
51             q.push(*ht.left);
52         }
53         if(ht.right!=NULL){
54             ht.right->deep=ht.deep+1;
55             q.push(*ht.right);
56         }
57         if(!ht.left && !ht.right){
58             sum+=ht.deep*ht.fred;
59         }
60     }   
61 }
62 int main(void)
63 {
64     char c[10005];
65     int t,n;
66     scanf("%d",&t);
67     while(t--)
68     {
69         scanf("%d%s",&n,c);
70         len=strlen(c);
71         c[len]=‘!‘;
72         sort(c,c+len);
73         cnt=1;
74         id=0;
75         for(int i=1;i<=len;i++)
76             if(c[i]!=c[i-1]){
77                 trie[id++].fred=cnt;
78                 cnt=1;
79             }else cnt++;
80         if(id==1){
81             if(len>n) puts("no");
82             else puts("yes");
83             continue;
84         }
85         huffman();
86         if(sum>n) puts("no");
87         else puts("yes");
88     }
89     return 0;
90 }

 1 //15MS    232K    984 B    G++    
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<queue>
 5 using namespace std;
 6 int main(void)
 7 {
 8     int t,n,r,len;
 9     int p[27];
10     char c[10005];
11     scanf("%d",&t);
12     while(t--)
13     {
14         memset(p,0,sizeof(p));
15         scanf("%d%s",&n,c);
16         len=strlen(c);
17         int judge=1;
18         for(int i=1;i<len;i++){
19             if(c[i]!=c[i-1]) judge=0; 
20         }
21         if(judge){
22             if(len>n) puts("no");
23             else puts("yes");
24             continue;
25         }
26         for(int i=0;i<len;i++)
27             p[c[i]-‘a‘]++;
28         priority_queue<int,vector<int>,greater<int> >Q;
29         int sum=0;
30         for(int i=0;i<27;i++) 
31             if(p[i]) Q.push(p[i]);
32         while(Q.size()>1){
33             int a=Q.top();
34             Q.pop();
35             int b=Q.top();
36             Q.pop();
37             sum+=a+b;
38             Q.push(a+b);
39         }
40         if(sum>n) puts("no");
41         else puts("yes");
42     }
43     return 0;
44 }