AcWing 148. 合并果子

2020-07-07  本文已影响0人  来到了没有知识的荒原

AcWing 148. 合并果子

哈夫曼/贪心

#include<iostream>
#include<queue>
using namespace std;

int main(){
    int n;
    cin>>n;
    priority_queue<int,vector<int>,greater<int>>heap;
    while(n--){
        int x;
        cin>>x;
        heap.push(x);
    }

    int res=0;
    while(heap.size()>1){
        int a=heap.top();
        heap.pop();
        int b=heap.top();
        heap.pop();
        res+=a+b;
        heap.push(a+b);
    }
    
    cout<<res;
    
    return 0;
}
上一篇下一篇

猜你喜欢

热点阅读