题目描述

哈夫曼编码中  平均码长=码长×码字出现的概率

如: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

来源

2009机考D题

#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 ;
}

最新文章

  1. 构建高可用ZooKeeper集群
  2. Codeforces CF#628 Education 8 D. Magic Numbers
  3. Use filter in outlook2013
  4. kali 在线教学群 第一次 公开课 小结(1)
  5. HDU 1141---Brackets Sequence(区间DP)
  6. U3D外包、Unreal4外包、VR外包就找北京动点飞扬软件
  7. JAVA 静态成员 static
  8. uva 10048 Audiophobia(最小生成树)
  9. springMVC从上传的Excel文件中读取数据
  10. org.apache.http.ProtocolException: Target host is not specified
  11. 高效线程池之无锁化实现(Linux C)
  12. 关于Action中ValidateXXX方法校验一次失败后\导致以后一直返回input视图的情况
  13. Google生活
  14. Inna and Sequence
  15. 懒省事的小明--nyoj55
  16. Sticks&lt;DFS&gt;
  17. iOS多线程——同步异步串行并行
  18. Linux 对信号的总结
  19. SQL UPDATE with INNER JOIN
  20. 出题人的手环(牛客练习赛38D 离散化+树状数组)

热门文章

  1. verilog behavioral modeling--sequential and parallel statements
  2. IE8 png图片黑色阴影的解决方案!
  3. 数据结构( Pyhon 语言描述 ) &mdash; &mdash;第11章:集和字典
  4. git commit 含有中文的代码,提示Warnning:Your console font probably doesn&#39;t support Unicode.......
  5. 关于django form验证是否用户名已存在
  6. intellij idea 17 log4j 中文乱码
  7. Leetcode 407.接雨水
  8. Python 频繁读取Mysql相关问题
  9. BZOJ 2300 [HAOI2011]防线修建 ——计算几何
  10. BZOJ 3205 [Apio2013]机器人 ——斯坦纳树