#2786. 哈夫曼树(Huffman Tree)

哈夫曼树(Huffman Tree)

题目描述

给定 ( N ) 个权值作为 ( N ) 个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。

现在,给定 ( N ) 个叶子结点的信息,请你构造哈夫曼树,并输出该树的带权路径长度。

输入格式

第一行包含整数 ( N ),表示叶子结点数量。

第二行包含 ( N ) 个整数,表示每个叶子结点的权值。

输出格式

输出一个整数,表示生成哈夫曼树的带权路径长度。

样例

样例输入

5
1 2 2 5 9

样例输出

37

数据范围与提示

  • (2N1000)( 2 \leq N \leq 1000 )
  • 叶子结点的权值范围 ([1, 100])