Huffman树:
题目链接:POJ1521
#include<stdio.h> #include<string.h> #include<queue> using namespace std; int t[100],len; char c[1000]; int huffman() { int a,b,c,sum=0; priority_queue<int,vector<int>,greater<int> >q;//priority_queue<int,vector<int>,greater<int> > q; for(int i=65;i<100;i++) { if(t[i]>0) q.push(t[i]); } while(q.size()>1) { a=q.top();q.pop(); b=q.top();q.pop(); c=a+b; sum+=c; q.push(c); } return sum?sum:len; } int main() { int sum; while(scanf("%s",c)!=EOF) { if(strcmp(c,"END")==0) break; memset(t,0,sizeof t); len=strlen(c); for(int i=0;i<len;i++) t[c[i]]++; sum=huffman(); printf("%d %d %.1f\n",len*8,sum,(double)len*8/sum); } return 0; }