sdut 3345ハフマン符号化&&優先キュー

Problem Description

文字の符号化方式はいろいろありますが、よく知られているASCII符号化のほか、ハフマン符号化(Huffman Coding)も符号化方式で、可変字長符号化です.この方法は,文字出現確率に完全に基づいて平均長が最も短い符号化を構築し,最適符号化と呼ぶ.ハフマン符号化は、データファイル圧縮によく用いられ、その圧縮率は通常20%〜90%である.あなたの任務はキーボードから入力した文字列に対してそのASCII符号化長とハフマン符号化長の比を求めることです.

Input

 
入力データは複数のグループがあり、各グループのデータは1行で、符号化する文字列を表す.

Output

 
対応文字
ASCII
コード長
la
,
huffman
コード長
lh
および
la/lh
の値
(
小数を1桁保持
)
を選択します.

Example Input

AAAAABCD
THE_CAT_IN_THE_HAT

Example Output

64 13 4.9
144 51 2.8

Hint

#include 
#include 
#include 
#include 
using namespace std;
int main()
{
    char ch[100];
    while(cin>>ch)
    {
        int max=0,ans[260]={0};
        priority_queue < int,vector,greater > Q;// 
        for(int i=0;imax)// ， 
                max=ch[i];
        }
        for(int j=0;j<=max;++j)// ， 
            if(ans[j])// 0 
                Q.push(ans[j]);
        int sum=0;
        while(!Q.empty())
        {
            int p=Q.top(),q;
            Q.pop();
            if(!Q.empty())
            {
                q=Q.top();
                Q.pop();
                sum+=p+q;
                Q.push(p+q);
            }
        }
        printf("%d %d %.1f
",strlen(ch)*8,sum,strlen(ch)*8.0/sum);
    }
}