【题解】UVa P10954 【Add All】

AD

STL建堆函数:http://www.cinema000.xyz/482.ruby

题意

就是经典的合并果子

分析

用一个堆就好了

代码

既然用一个堆,那就用STL的函数建一个堆吧!

#include<cstdio>
#include<algorithm>
#include<functional>
#include<vector>

namespace OI{
    using std::vector;
    using std::push_heap;
    using std::pop_heap;
    using std::greater;
    using std::less;
}
using namespace OI;

template<class T>
class Heap{
    public:vector<T> v;
    public:Heap(){
        v.reserve(666666);
    }
    public:~Heap(){
        v.clear();
    }

    public:void push(T key){
        v.push_back(key);
        push_heap(v.begin(),v.end(),greater<T>());
    }

    public:void pop(){
        pop_heap(v.begin(),v.end(),greater<T>());
        v.pop_back();
    }

    public:T front(){
        return v[0];
    }
}; 

int main(){
    int n,x;

    while(scanf("%d",&n) == 1 && n){
        Heap<int> h = Heap<int>();
        for(int i = 0;i < n;i++){
            scanf("%d",&x);
            h.push(x);
        }
        int ans = 0;
        for(int i = 0;i < n - 1;i++){
            int a = h.front();h.pop();
            int b = h.front();h.pop();
            ans += a + b;
            h.push(a + b);
        }
        printf("%d\n",ans);
    }

    return 0;
}