#2786. 哈夫曼树(Huffman Tree)
哈夫曼树(Huffman Tree)
题目描述
给定 ( N ) 个权值作为 ( N ) 个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。
现在,给定 ( N ) 个叶子结点的信息,请你构造哈夫曼树,并输出该树的带权路径长度。
输入格式
第一行包含整数 ( N ),表示叶子结点数量。
第二行包含 ( N ) 个整数,表示每个叶子结点的权值。
输出格式
输出一个整数,表示生成哈夫曼树的带权路径长度。
样例
样例输入
5
1 2 2 5 9
样例输出
37
数据范围与提示
- 叶子结点的权值范围 ([1, 100])