2193 - 哈夫曼树

题目描述

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

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

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

输入

输入的第一行包含一个正整数 nn≤100)。

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

输出

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

样例

输入

5
5 3 8 2 9

输出

59
来源

二叉树

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 入门


上一题 下一题