定义：
给定数列｛ai} 哈夫曼数是一棵二叉树，满足数列中的所有的数都是它的叶节点，且每一个叶节点的权值*它到根的距离之和最短。
构造方法：
将原数列看成一个森林，每次挑出最小的两个节点合并，直到只剩下一个节点，就构造好了一颗哈夫曼树。 （证明略～）
示例代码：
#include<cstdio>
#include<string>
#include<queue>
using namespace std;
const int maxn=
2000005;
int n,tot,a[maxn],fa[maxn];
long long ans;
struct dyt{
int x,id;
bool operator <(
const dyt &b)
const{
return x>b.x;}
};
priority_queue<dyt> hep;
inline int read(){
int x=
0;
char ch=getchar();
while (ch<
'0'||ch>
'9') ch=getchar();
while (ch>=
'0'&&ch<=
'9') x=x*
10+ch-
48,ch=getchar();
return x;
}
int dfs(
int x){
if (fa[x]==
0)
return 0;
int s=dfs(fa[x]);
return s+
1;
}
int main(){
n=read(); tot=n;
for (
int i=
1;i<=n;i++) {
a[i]=read();
dyt x; x.x=a[i],x.id=i; hep.push(x);
}
while (hep.size()>
1) {
dyt x,y,z; x=hep.top(); hep.pop(); y=hep.top(); hep.pop();
tot++; z.x=x.x+y.x; z.id=tot; fa[x.id]=fa[y.id]=tot;
hep.push(z);
}
for (
int i=
1;i<=n;i++) ans+=
1ll*dfs(i)*a[i];
printf(
"%lld\n",ans);
return 0;
}
