要点：哈夫曼编码 求最后编码完成之后编码的长度
解决方法： 即为所有度为2的节点的权重的和。。避免了一次次的相加
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<queue> 5 #include<cstring> 6 #include<vector> 7 using namespace std; 8 int main(){ 9 char str[1000]; 10 while(cin>>str){ 11 if(!strcmp(str,"END")) 12 break; 13 int num[27]; 14 memset(num,0,sizeof(num)); 15 int len = strlen(str); 16 for(int i=0;i<len;i++){ 17 if(str[i]=='_') 18 num[26]++; 19 else 20 num[str[i]-'A']++; 21 } 22 priority_queue<int,vector<int >,greater<int > > q ; 23 for(int i=0;i<27;i++) 24 if(num[i]){ 25 // cout<<num[i]<<endl; 26 q.push(num[i]); 27 } 28 //cout<<q.top()<<endl; 29 int ssum = len*8; 30 int sum=0; 31 if(q.size()==1) sum = q.top(); 32 while(1){ 33 int a ,b; 34 a = q.top(); 35 q.pop(); 36 if(q.empty()) 37 break; 38 b = q.top(); 39 q.pop(); 40 sum += a+b;//编码的长度，正好等于所有度为2的节点的和 41 q.push(a+b); 42 } 43 printf("%d %d %.1lf ",ssum,sum,ssum*1.0/sum); 44 } 45 return 0; 46 }