hdu1053

#include<iostream> #include<algorithm> using namespace std; bool cmp(int a,int b) { return a>b; //从大到小排序 } int a[30],m; char s[1005]; int huffman() { int n,i,t; memset(a,0,sizeof(a)); for(i=0;i<m;i++) //统计频率 if(s[i]=='_') a[0]++; else a[s[i]-'A'+1]++; sort(a,a+27,cmp); //频率从小到大排序 for(i=0;;i++) if(!a[i]) break; n=i; t=0; for(i=n-1;i>0;i--) //注意频率最低的编码为全1，即类似于111111... { a[i-1]=a[i]+a[i-1]; //构造huffman树的思想 t+=a[i-1]; sort(a,a+i,cmp); } if(n==1) t=a[0]; return t; } int main() { int t; while(gets(s)&& strcmp("END",s)) { m=strlen(s); t=huffman(); printf("%d %d %.1lf\n",8*m,t,8.0*m/t); } return 0; }