心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
哈夫曼树。使用堆来维护。
以下是我的代码:
/*
 * 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;
}
posted on 2011-08-05 23:59 lee1r 阅读(626) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理