hdoj 1053 Entropy（用哈夫曼编码）优先队列

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1053

讲解：

　　题意：给定一个字符串，根据哈夫曼编码求出最短长度，并求出比值。

思路：就是哈夫曼编码。把单个字符出现次数作为权值。

AC代码：

 1 #include <iostream>
 2 #include <string>
 3 #include <queue>
 4 #include <cstdio>
 5 using namespace std;
 6 
 7 class node{
 8 public:
 9     int key; //a,b,c...
10     int count;//频率
11     int p;//父亲结点
12     friend bool operator < (const node &a, const node &b)
13     {
14         if(b.count < a.count)
15             return true;
16         else
17             return false;
18     }
19 };
20 
21 int value(char c)
22 {
23     if(c=='_')
24         return 26;
25     else
26         return(c-'A');
27 }
28 int main()
29 {
30     string str;
31     cin >> str;
32     while(str!="END")
33     {
34         node c[60];
35         for(int i=0;i<60;i++)
36         {
37             c[i].key=i;
38             c[i].count=0;
39         }
40         int length=str.length();
41         priority_queue<node> q;
42         for(int i=0;i<length;i++)
43         {
44             (c[value(str.at(i))]).count++;
45         }
46         for(int i=0;i<=26;i++)
47         {
48             if(c[i].count!=0)
49                 q.push(c[i]);
50         }
51         if(q.size()==1)
52         {
53             printf("%d %d 8.0
",8*length,length);
54         }
55         else
56         {
57             int high=0;
58             int n=27;
59             while(q.size()>1)
60             {
61                 node s1=q.top();
62                 q.pop();
63                 node s2=q.top();
64                 q.pop();
65                 c[n].count=s1.count+s2.count;
66                 c[s1.key].p=n;
67                 c[s2.key].p=n;
68                 high=high+c[n].count;
69                 q.push(c[n]);
70                 n++;
71             }
72             printf("%d %d %.1lf
",8*length,high,(((double)(8*length))/((double)high)));
73         }
74         cin >> str;
75     }
76 }