2192: 【入门】哈夫曼树

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:4 通过:4

题目描述

哈夫曼树的定义是:一棵具有n个带权叶结点的二叉树,使得所有叶结点的带权路径长度(叶结点×叶结点到根结点的路径长度)之和最小,这样的二叉树被称为最优二叉树,也称哈夫曼树。

比如:有4个结点的权值是5 4 2 9,可以构建出如下三颗不同的二叉树,第2棵二叉树的带权路径长度是最小的。

请读入一个整数n,代表叶结点的数量,再读入n个整数,代表叶结点的权值,请求出对应哈夫曼树的带权路径长度。

输入格式

输入的第一行包含一个正整数n(n<=100)。

接下来是n个正整数,表示n个叶结点的权值,每个数不超过1000。

输出格式

输出构造出的哈夫曼树的带权路径长度。

输入样例 复制

5
5 3 8 2 9

输出样例 复制

59

分类标签