题目大意：原题链接
锯木板，锯木板的长度就是花费。比如你要锯成长度为8 5 8的木板，最简单的方式是把21的木板割成13，8，花费21，再把13割成5，8，花费13，共计34，当然也可以先割成16，5的木板，花费21，再把16割两个8，花费16，总计37，现在就是问你花费最少的情况。
思路：转化为哈弗曼树
解法一：AC
#include<cstdio>
#include<algorithm>
#define maxn 20010
using namespace std;
int n,a[maxn];
void get_min(int x)
{
int p=x;
for(int i=x+;i<=n;i++){
if(a[i]<a[p])
p=i;
}
swap(a[p],a[x]);
}
int main()
{
while(scanf("%d",&n)!=EOF){
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
long long ans=;
for(int i=;i<n;i++){
get_min(i);
ans+=a[i];
get_min(i+);
ans+=a[i+];
a[i+]+=a[i];
}
printf("%lld",ans);
}
}
解法二：优先队列AC
#include<cstdio>
#include<queue>
using namespace std;
int n,d;
priority_queue<int,vector<int>,greater<int> > que;
int main()
{
while(scanf("%d",&n)!=EOF){
while(!que.empty())
que.pop();
for(int i=;i<=n;i++){
scanf("%d",&d);
que.push(d);
}
long long ans=;
while(que.size()!=){
int x=que.top();
que.pop();
int y=que.top();
que.pop();
ans+=(x+y);
que.push(x+y);
}
printf("%lld\n",ans);
}
}