题目链接：http://poj.org/problem?id=1521
代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<string.h> 5 #include<queue> 6 using namespace std; 7 const int maxn = 1e7+5; 8 char s[maxn]; 9 int main() 10 { 11 while (scanf("%s",s)&&strcmp(s,"END")) 12 { 13 int t=1; 14 int len=strlen(s); 15 sort(s,s+len); 16 priority_queue<int ,vector<int> ,greater<int> > q;//将每个字符出现的频次放入优先队列 17 for(int i = 1 ; i < len ; i++) 18 { 19 if(s[i-1]!=s[i]) 20 { 21 q.push(t); 22 t=1; 23 } 24 else t++; 25 } 26 q.push(t); 27 int ans=0; 28 while(q.size()>1)//最终队列中只会剩下一个根结点的值，不必算在内 29 { 30 int a=q.top();q.pop(); 31 int b=q.top();q.pop(); 32 ans+=a+b;//每次只加a+b就能得到频次*深度的原因是深度为dep的频次在之后会被加到其他树上，会多次计算 33 q.push(a+b); 34 } 35 if(ans==0)ans=q.top(); 36 q.pop(); 37 int ans1=len*8; 38 double ans3=(double)ans1/ans; 39 printf("%d %d %.1lf ",ans1,ans,ans3); 40 } 41 }