HDU1053，POJ1521，ZOJ1117 Entropy 哈夫曼编码

题目大意：输入一个只包含大写字母和下划线的字符序列，把每个字符进行编码，求其最少编码长度。

这题和HDU2527一样，算是典型的哈夫曼编码问题。构造出此序列的最优二叉树即可。

代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 999999999
using namespace std;
int main()
{
char str[100];
int i,ans,w[30];
while(scanf("%s",str))
{
if(strcmp(str,"END")==0)
break;
int len=strlen(str);
for(i=0;i<30;i++) w[i]=0;
for(i=0;i<len;i++)
if(str[i]=='_') w[27]++;
else w[str[i]-'A']++;
for(i=0;i<30;i++)
if(w[i]==0)
w[i]=INF;
sort(w,w+30);
ans=0;
for(i=0;i<30;i++)
if(w[i]==INF)
break;
if(i==1)
ans=w[0];
while(w[1]<INF)
{
w[0]+=w[1];
w[1]=INF;ans+=w[0];
sort(w,w+30);
}
printf("%d %d %.1fn",8*len,ans,(double)8*len/ans);
}
return 0;
}

最后

以上就是美好盼望最近收集整理的关于HDU1053，POJ1521，ZOJ1117 Entropy 哈夫曼编码的全部内容，更多相关HDU1053，POJ1521，ZOJ1117内容请搜索靠谱客的其他文章。