1 /*

 2 Author:    Leo.W

 3 Descriptipn:对输入字符串【长度不知，仅含26个大写英文字母和一个空格表示符‘_’，共27种字符】,

 4             统计每种字符出现频度，按哈夫曼编码原理给出最小的编码位数之和，得出与8位固定字长

 5             编码的比率【保留一位小数】。

 6 How to Do:    哈夫曼编码原理的理解及优先队列的运用<priority_queue>,引用头文件<queue>

 7   */

 8 #include <iostream>

 9 #include <string.h>

10 #include <queue>

11 #include <algorithm>

12 using namespace std;

13 #define lenth 300

14 int main(){

15     //freopen("in.txt","r",stdin);

16     char str[1000];//输入字符串

17     while(scanf("%s",str),strcmp(str,"END")!=0){

18         int lenStr=strlen(str);

19         int worse=lenStr<<3;//固定字长编码所需的总位数

20         char ch[lenth];int lenCh=0;//输入字符的种类

21         int i,j,num[lenth];//对应每种字符的数目，无需关注具体对应的是哪个字符，只需记录数目即可。【为什么呢？】

22         memset(num,0,lenth);//字符数目数组初始置零

23         //对字符串逐个统计出现次数

24         for(i=0;i<lenStr;i++){

25             for(j=0;j<lenCh;j++){

26                 if(str[i]==ch[j]){

27                     num[j]++;break;

28                 }

29             }

30             if(j==lenCh){

31                 ch[j]=str[i];num[j]++;lenCh++;

32             }

33         }

34         sort(num,num+lenCh);//对得到的字符数目【大于零，即至少出现过一次，才存在统计必要】序列进行升序快排

35         priority_queue<int,vector<int>,greater<int> >    que;//对于int整型数据，进行自小至大的优先级排列

36         for(i=0;i<lenCh;i++)    que.push(num[i]);

37         int sum=0;

38         while(true){

39             int aa=que.top();    que.pop();

40             if(que.empty())    {

41                 if(lenCh==1)    sum=aa;

42                 break;

43             }

44             int bb=que.top();    que.pop();

45             sum+=aa+bb;        que.push(aa+bb);

46         }

47         printf("%d %d %.1lf\n",worse,sum,worse*1.0/sum);

48     }

49     return 0;

50 }