Fence Repair

POJ

哈夫曼树模板题，记得开long long就行了.

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
priority_queue<int,vector<int>,greater<int> >q;
inline void Huffman(int n){
    long long ans=0;
    while(n>1){
        int tot=0;
        for(int i=1;i<=2;++i){
            tot+=q.top();q.pop();
        }
        q.push(tot);ans+=tot;n--;
    }
    printf("%lld
",ans);
}
int main(){
	int n=read();
	for(int i=1;i<=n;++i){int a=read();q.push(a);}
	Huffman(n);
    return 0;
}