哈夫曼樹(shù)。使用堆來(lái)維護(hù)。
以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/5 23:46:40
* File Name: poj3253.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-8);
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(20007);
int n;
int64 ans;
int main()
{
//freopen("data.in","r",stdin);
while(scanf("%d",&n)==1)
{
priority_queue< int,vector<int>,greater<int> > q;
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
q.push(t);
}
ans=0;
while(q.size()>1)
{
int t(q.top());q.pop();
t+=q.top();q.pop();
q.push(t);
ans+=t;
}
//ans+=q.top();
cout<<ans<<endl;
}
return 0;
}