哈夫曼编码
题号:NC233601
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给出一个有n种字符组成的字符串,其中第i种字符出现的次数为a_i。请你对该字符串应用哈夫曼编码,使得该字符串的长度尽可能短,求编码后的字符串的最短长度。

输入描述:

第一行输入一个整数n (),表示字符种数。
第二行输入n个整数a_i (),表示每种字符的出现次数。

输出描述:

输出一行一个整数,表示编码后字符串的最短长度。
示例1

输入

复制
3
1 2 3

输出

复制
9

说明

三种字符的哈夫曼编码分别为["00","01","1"]时,长度最短,最短长度为9。