PKU 1521 Entropy(简单哈弗曼树_水过)

题目大意：原题链接

给你一个字符串，首先是计算出一个按正常编码的编码长度，其次是计算出一个用霍夫曼编码的编码长度，最后求正常编码的长度除以霍夫曼编码长度的比值，保留一位小数。

解题思路：需要知道

1.正常的编码长度的话，由于都是ASCII码值所以编码长度都为8，所以总长度就是8*字符串的长度Len就行。

2.哈弗曼树带权路径之和WPL=非叶子节点权值之和

刚开始一直不明白运行结果都正确了，为什么Compile Error，后来才知道原来iostream头文件不包含printf，所以又加上了cstdio头文件，也给了自己一个启发：

以后头文件中可以两个都写，这样都能用cin,cout,scanf,printf都能用，很方便

#include<queue>

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

string str;

int ans,s[];

priority_queue<int,vector<int>,greater<int> > que;

int main()

{

    while(cin>>str){

        if(str=="END") return ;

        memset(s,,sizeof(s));

        sort(str.begin(),str.end());

        char ch=str[];

        int len=str.length(),cnt=;

        while(!que.empty()) que.pop();

        for(int i=;i<len;i++){

            if(str[i]==ch) cnt++;

            else{

                ch=str[i];

                que.push(cnt);

                cnt=;

            }

        }

        que.push(cnt);

        if(que.size()==) ans=que.top();

        else{

            ans=;

            while(que.size()!=){

                int x=que.top();

                que.pop();

                int y=que.top();

                que.pop();

                ans+=(x+y);

                que.push(x+y);

            }

        }

        double rate=(double)*len/ans;

        printf("%d %d %.1f\n",*len,ans,rate);

    }

}