1 /*

 2 Author:    Leo.W

 3 Descriptipn:對(duì)輸入字符串【長(zhǎng)度不知，僅含26個(gè)大寫英文字母和一個(gè)空格表示符‘_’，共27種字符】,

 4             統(tǒng)計(jì)每種字符出現(xiàn)頻度，按哈夫曼編碼原理給出最小的編碼位數(shù)之和，得出與8位固定字長(zhǎng)

 5             編碼的比率【保留一位小數(shù)】。

 6 How to Do:    哈夫曼編碼原理的理解及優(yōu)先隊(duì)列的運(yùn)用<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;//固定字長(zhǎng)編碼所需的總位數(shù)

20         char ch[lenth];int lenCh=0;//輸入字符的種類

21         int i,j,num[lenth];//對(duì)應(yīng)每種字符的數(shù)目，無需關(guān)注具體對(duì)應(yīng)的是哪個(gè)字符，只需記錄數(shù)目即可。【為什么呢？】

22         memset(num,0,lenth);//字符數(shù)目數(shù)組初始置零

23         //對(duì)字符串逐個(gè)統(tǒng)計(jì)出現(xiàn)次數(shù)

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);//對(duì)得到的字符數(shù)目【大于零，即至少出現(xiàn)過一次，才存在統(tǒng)計(jì)必要】序列進(jìn)行升序快排

35         priority_queue<int,vector<int>,greater<int> >    que;//對(duì)于int整型數(shù)據(jù)，進(jìn)行自小至大的優(yōu)先級(jí)排列

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 }