题目大意：原题链接
锯木板，锯木板的长度就是花费。比如你要锯成长度为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+1;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=1;i<=n;i++) scanf("%d",&a[i]); long long ans=0; for(int i=1;i<n;i++){ get_min(i); ans+=a[i]; get_min(i+1); ans+=a[i+1]; a[i+1]+=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=1;i<=n;i++){ scanf("%d",&d); que.push(d); } long long ans=0; while(que.size()!=1){ int x=que.top(); que.pop(); int y=que.top(); que.pop(); ans+=(x+y); que.push(x+y); } printf("%lld\n",ans); } }
原文：http://www.cnblogs.com/freinds/p/6421035.html