2772: 哈夫曼树
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：7
解决：6
题目描述
哈夫曼树的定义是：一棵具有 n 个带权叶结点的二叉树，使得所有叶结点的带权路径长度（叶结点 × 叶结点到根结点的路径长度）之和最小，这样的二叉树被称为最优二叉树，也称哈夫曼树。
比如：有 4 个结点的权值是5 4 2 9，可以构建出如下三颗不同的二叉树，第 2 棵二叉树的带权路径长度是最小的。
请读入一个整数n，代表叶结点的数量，再读入n个整数，代表叶结点的权值，请求出对应哈夫曼树的带权路径长度。
比如：有 4 个结点的权值是5 4 2 9，可以构建出如下三颗不同的二叉树，第 2 棵二叉树的带权路径长度是最小的。
请读入一个整数n，代表叶结点的数量，再读入n个整数，代表叶结点的权值，请求出对应哈夫曼树的带权路径长度。
输入
输入的第一行包含一个正整数 n（n≤100）。
接下来是 n 个正整数，表示 n 个叶结点的权值，每个数不超过 1000 。
接下来是 n 个正整数，表示 n 个叶结点的权值，每个数不超过 1000 。
输出
输出构造出的哈夫曼树的带权路径长度。
样例输入 复制
5
5 3 8 2 9样例输出 复制
59