http://acm.hdu.edu.cn/showproblem.php?pid=1053
Huffman问题利用STL中的priority_queue解决；
1 #include<stdio.h> 2 #include<iostream> 3 #include<string> 4 #include<algorithm> 5 #include<map> 6 #include<queue> 7 using namespace std; 8 9 struct cmp 10 { 11 bool operator()(const int a, const int b) 12 { 13 return a > b; 14 } 15 }; 16 int solve(string str) 17 { 18 priority_queue< int,vector<int>,cmp >que; 19 map<char, int> mymap; 20 int i; 21 for(i =0; i < str.size(); i++) 22 { 23 mymap[str[i]]++; 24 } 25 26 map<char,int>::iterator it = mymap.begin(); 27 while(it != mymap.end()) 28 { 29 //printf("%c %d ",it->first,it->second); 30 que.push(it->second); 31 it++; 32 } 33 34 int weight = 0; 35 if(que.size() == 1) 36 return que.top(); 37 38 while(que.size() != 1) 39 { 40 int a,b; 41 a = que.top(); 42 que.pop(); 43 b = que.top(); 44 que.pop(); 45 46 weight += a+b; 47 que.push(a+b); 48 } 49 return weight; 50 } 51 int main() 52 { 53 int weight; 54 string str; 55 while(cin>>str) 56 { 57 if(str == "END") 58 break; 59 weight = solve(str); 60 printf("%d %d %.1lf ",8*str.size(),weight,8.0*str.size()/weight); 61 } 62 return 0; 63 }