http://acm.hdu.edu.cn/showproblem.php?pid=1053
Huffman问题利用STL中的priority_queue解决;
#include<stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
using namespace std; struct cmp
{
bool operator()(const int a, const int b)
{
return a > b;
}
};
int solve(string str)
{
priority_queue< int,vector<int>,cmp >que;
map<char, int> mymap;
int i;
for(i =; i < str.size(); i++)
{
mymap[str[i]]++;
} map<char,int>::iterator it = mymap.begin();
while(it != mymap.end())
{
//printf("%c %d\n",it->first,it->second);
que.push(it->second);
it++;
} int weight = ;
if(que.size() == )
return que.top(); while(que.size() != )
{
int a,b;
a = que.top();
que.pop();
b = que.top();
que.pop(); weight += a+b;
que.push(a+b);
}
return weight;
}
int main()
{
int weight;
string str;
while(cin>>str)
{
if(str == "END")
break;
weight = solve(str);
printf("%d %d %.1lf\n",*str.size(),weight,8.0*str.size()/weight);
}
return ;
}