学步园

哈夫曼水题，就是题目爆长，涨英文了。

code：

#include <set>
#include <cstring>
#include <cstdio>
using namespace std;

char buf[300];
multiset<int> s;
int n,cnt[151];
//采用2进制的哈夫曼,clen进制数
int huffman(char str[],int clen)
{
    s.clear();
    memset(cnt,0,sizeof(cnt));
    int i,tmp,sum;
    for(i=0;i<strlen(str);i++)
    {
        cnt[str[i]]++;
    }
    for(i=0;i<=150;i++)
    {
        if(cnt[i])
        {
            s.insert(cnt[i]);
        }
    }
    if(s.size()==1)
    {
        return *s.begin();
    }
    else
    {
        sum=0;
        while(s.size()>1)
        {
            tmp=0;
            for(i=0;i<clen;i++)
            {
                tmp+=*s.begin();
                s.erase(s.begin());
            }
            s.insert(tmp);
            sum+=tmp;
        }
        return sum;
    }
}
int main()
{
    int dsum,sum;
    while(gets(buf))
    {
        if(!strcmp(buf,"END")) break;
        dsum=strlen(buf)*8;
        sum=huffman(buf,2);
        printf("%d %d %.1f\n",dsum,sum,dsum*1.0/sum);
    }
    return 0;
}