Skip to content

1126: 骆源的哈夫曼树

题目

题目描述

骆源,上海交通大学计算机系教授。兼任美国数学评论评论员、第五届亚欧信息论研讨会AEW5联合主席。承担过国家自然科学基金、教育部留学回国人员基金及德国国家科学基金DFG的项目。对于我们来说,骆源的离散数学课是一朵奇葩。 这道题目是骆源的哈夫曼树,哈夫曼树大家都记得是什么吧(翁老师又讲过一次,如果不记得就翻翻书吧)。但是作为骆源的哈夫曼树,自然要有些不同。骆源的哈夫曼树可以有N个分叉(注意,有时要补零!)。哈夫曼树的要求和构造方式和二叉并没有什么不同(除了要补零之外)。

为了方便,这道题并不需要你输出具体的编码,只需要你计算出最后的WPL=∑F[i]×len[i] (带权路径长度,实际上就是所有编码的长度乘上权值。)即可。

本题不允许使用STL。

输入格式

第一行为两个整数N、M,N≤100000。表示数据的数量,1<M≤1000,表示哈夫曼树的分叉数。 接下来N行,每行1个数,F[i]≤10000,表示第i个数据的权值。

输出格式

一行, 一个整数, 代表WPL的值。保证结果在long long的范围内。

样例输入

4 3
1
2
3
4

样例输出

13

先补1个零。 哈夫曼编码: - 0:00 - 1:01 - 2:02 - 3:1 - 4:2

Output=1 * 2 + 2 * 2 + 3 * 1 + 4 * 1 = 13

数据范围

对于30%的数据, n <= 1000。另外,对于50%的数据,m=2。

有时要补零。大家还记得要补几个零吗?

另外,要ac掉100%的数据,请用堆优化吧(其实就是传说中的优先级队列)另外为了表示对骆源的尊敬,不允许使用STL哦^_^。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!