4517: 【入门】哈夫曼树(2193)

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

哈夫曼树的定义是：一棵具有 lns="http://www.w3.org/1998/Math/MathML">n 个带权叶结点的二叉树，使得所有叶结点的带权路径长度（叶结点 lns="http://www.w3.org/1998/Math/MathML">× 叶结点到根结点的路径长度）之和最小，这样的二叉树被称为最优二叉树，也称哈夫曼树。

比如：有 lns="http://www.w3.org/1998/Math/MathML">4 个结点的权值是lns="http://www.w3.org/1998/Math/MathML">5 lns="http://www.w3.org/1998/Math/MathML">4 lns="http://www.w3.org/1998/Math/MathML">2 lns="http://www.w3.org/1998/Math/MathML">9，可以构建出如下三颗不同的二叉树，第 lns="http://www.w3.org/1998/Math/MathML">2 棵二叉树的带权路径长度是最小的。

请读入一个整数 lns="http://www.w3.org/1998/Math/MathML">n ，代表叶结点的数量，再读入 lns="http://www.w3.org/1998/Math/MathML">n 个整数，代表叶结点的权值，请求出对应哈夫曼树的带权路径长度。

输入

输入的第一行包含一个正整数 lns="http://www.w3.org/1998/Math/MathML">n（lns="http://www.w3.org/1998/Math/MathML">2≤n≤100）。

接下来是 lns="http://www.w3.org/1998/Math/MathML">n 个正整数，表示 lns="http://www.w3.org/1998/Math/MathML">n 个叶结点的权值，每个数不超过 lns="http://www.w3.org/1998/Math/MathML">1000 。

输出

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

样例输入 复制 

5
5 3 8 2 9

样例输出 复制 

59

来源/分类

提交提交记录统计露一手!