题解 P1090 【合并果子】

Skywind · 2019-08-13 11:27:28 · 题解

本题使用优先队列

#include<bits/stdc++.h>//如果用#include<iostream>，要加上#include<queue>
using namespace std;
int main(){
    int n,zjs,ks;
    priority_queue<int,vector<int>,greater<int> > a;//声名它是小根堆
    cin>>n;
    for(int i=1;i<=n;i++){//输入到小根堆，会自动从小到大排序
        cin>>zjs;
        a.push(zjs);
    }
    ks=0;//计算总共用的力气
    while(a.size()>=2){
        int u1,u2;
        u1=a.top();//取出当前最小的
        a.pop();//取完后删掉
        u2=a.top();//取出当前最小的
        a.pop();//取完后删掉
        ks=ks+u1+u2;加起来放在ks里
        a.push(ks);//把ks再放回去
    }
    cout<<ks;//输出答案
    return 0;
}