Skip to content

14185: 【原4185】Huffman Tree

题目

题目描述

author: DS TA 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4185

Description

给定N个权重作为叶子节点,请你构建一棵哈夫曼树。 如果你需要排序,请使用堆帮助你降低时间复杂度。

Input Format

输入文件N+1行。

第一行包括一个正整数N,N是叶子节点的个数。(1<=n<=10000)

第2~N+1行包括N个int数据,代表节点权重w[i]。(1<=w[i]<=100000)

Output Format

输出所有节点权重乘长度的总和,即$$\sum_{i=1}^N w[i]\times \textrm{len}[i]$$。

Sample1 Input

4
1
2
3
4

Sample1 Output

19

Sample1 Explanation

哈夫曼树如下:
      10
     /  \
    6    4
   / \
  3   3  
 / \    
1   2
结果为1*3+2*3+3*2+4*1=19.

Sample2 Input

5
1 
2
3
2
4

Sample2 Output

27

Sample2 Explanation

哈夫曼树如下:

        12
      /    \
     5      7  
    / \    / \
   3   2  4   3
  / \   
 1   2
结果为1*3+2*3+2*2+3*2+4*2=27.

Limits

输入格式保证合法,输入数据不一定有序。

Oops! 本题目还没有解答!

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

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

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