poj 1521 Entropy
#include <iostream> #include <queue> #include <string> #include <stdio.h> using namespace std; string s; int k=0; struct node{ int w; int parent; int key; friend bool operator < (const node & a,const node & b){ if(b.w<a.w)return true; else return false; } }alp[60]; int value(char c){ if(c=='_')return 26; else return c-'A'; } void huf(){ int i,j; int length=s.length(); priority_queue<node>q; for(i=0;i<length;i++) alp[value(s[i])].w++; for(i=0;i<=26;i++){ if(alp[i].w!=0){ q.push(alp[i]); } } if(q.size()==1) printf("%d %d 8.0\n",8*length,length); else { j=27; while(q.size()>1){ node s1=q.top(); q.pop(); node s2=q.top(); q.pop(); alp[j].w=s1.w+s2.w; alp[s1.key].parent=j; alp[s2.key].parent=j; q.push(alp[j]); j++; } int res=0; for(int ii=0;ii<27;ii++){ if(alp[ii].w!=0){ int len=1; int par=alp[ii].parent; while(par!=j-1){ len++; par=alp[par].parent; } res+=len*alp[ii].w; } } double dd=8*length; printf("%d %d %.1lf\n",8*length,res,dd/res); } } int main() { while(cin>>s&&s!="END"){ int i; for(i=0;i<60;i++){ alp[i].w=0; alp[i].key=i; } huf(); } return 0; }