BUPT复试专题—哈夫曼编码(2009)
2024-09-29 23:06:35
题目描述
哈夫曼编码中 平均码长=码长×码字出现的概率
如:ABCDE 五个字符的出现次数分别为50 20 5 10 15
那么,其哈夫曼编码为A:0 B:10 C:1110 D:1111 E:110
该哈夫曼编码的平均码长=(50*1+20*2+5*4+10*4+15*3)/100=1.95
输入
有多组输入,每组两行
第一行:字符的个数 N
第二行:N 个以空格隔开的数,表示这 N 个字符中每个字符出现次数
输出
输出该哈夫曼编码的平均码长,保留两位小数
样例输入
5
50 20 5 10 15
样例输出
1.95
来源
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int a[];
char s[];
struct node
{
int w;
friend bool operator <(node aa, node bb) //<为从大到小排列,>为从小到大排列
{
return aa.w > bb.w;
}
};
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(a, , sizeof(a));
int num=,len=n;
for(int i=;i<=n;i++) //题目已知每一种字母有多少个,没已知要自己数
cin>>a[i];
priority_queue <node> q;
for(int i=;i<;i++)
{
num+=a[i];
node b;
b.w=a[i];
if(a[i])
q.push(b);
}
int res;
if(q.size() == )
res = len;
else
{
res = ;
while(q.size() > )
{
int aa = q.top().w; q.pop();
int bb = q.top().w; q.pop();
res += (aa + bb);
node b;
b.w = aa + bb;
q.push(b);
}
}
double temp=double(res)/(double)num;
printf("%.2lf\n",temp);
}
return ;
}
最新文章
- 构建高可用ZooKeeper集群
- Codeforces CF#628 Education 8 D. Magic Numbers
- Use filter in outlook2013
- kali 在线教学群 第一次 公开课 小结(1)
- HDU 1141---Brackets Sequence(区间DP)
- U3D外包、Unreal4外包、VR外包就找北京动点飞扬软件
- JAVA 静态成员 static
- uva 10048 Audiophobia(最小生成树)
- springMVC从上传的Excel文件中读取数据
- org.apache.http.ProtocolException: Target host is not specified
- 高效线程池之无锁化实现(Linux C)
- 关于Action中ValidateXXX方法校验一次失败后\导致以后一直返回input视图的情况
- Google生活
- Inna and Sequence
- 懒省事的小明--nyoj55
- Sticks<;DFS>;
- iOS多线程——同步异步串行并行
- Linux 对信号的总结
- SQL UPDATE with INNER JOIN
- 出题人的手环(牛客练习赛38D 离散化+树状数组)
热门文章
- verilog behavioral modeling--sequential and parallel statements
- IE8 png图片黑色阴影的解决方案!
- 数据结构( Pyhon 语言描述 ) &mdash; &mdash;第11章:集和字典
- git commit 含有中文的代码,提示Warnning:Your console font probably doesn&#39;t support Unicode.......
- 关于django form验证是否用户名已存在
- intellij idea 17 log4j 中文乱码
- Leetcode 407.接雨水
- Python 频繁读取Mysql相关问题
- BZOJ 2300 [HAOI2011]防线修建 ——计算几何
- BZOJ 3205 [Apio2013]机器人 ——斯坦纳树