HDU 2527 哈夫曼树

Safe Or Unsafe
http://acm.hdu.edu.cn/showproblem.php?pid=2527
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<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
char cnt[30];
int main(){
        int T;
        while(scanf("%d",&T)){
                int n;
                string s;
                while(T--){
                        cin>>n>>s;
                        memset(cnt,0,sizeof(cnt));
                        for(int i=0;s[i];i++)
                                cnt[s[i]-'a']++;
                        priority_queue<int,vector<int>,greater<int> >que;
                        for(int i=0;i<26;i++)
                                if(cnt[i])
                                        que.push(cnt[i]);
                        int ans=0,sum;
                        if(que.size()==1){//只有一个字母情况下只需要加上个数
                                ans=que.top();
                        }else{
                                while(que.size()>1){//合并最小的两个子结点
                                        // 取出前两个小的
                                        int t1=que.top();
                                        que.pop();
                                        int t2=que.top();
                                        que.pop();
                                        //求总和然后重新插入
                                        sum=t1+t2;
                                        que.push(sum);
                                        //每合并一次相当于上一层，将数字再加一次，最终就等价于权值乘以层数
                                        ans+=sum;
                                }
                        }
                        //cout<<ans<<endl;
                        if(ans<=n)
                                printf("yes
");
                        else
                                printf("no
");
                }
        }
        return 0;
}