G19|合并果子题解——STL优先队列法

G18|发牌游戏题解——STL优先队列法

较详细题解(具体讲解在代码里)

使用基础STL优先队列

·priority_queue<int,vector<int>,greater<int>>qu//较小的值在队首
·qu.push(x)//入优先队列并排序
·qu.top()//获取优先队列首值
·qu.pop()//删除优先队列首值
·qu.size()//获取优先队列长度

综上，写出代码：

#include <bits/stdc++.h>
#include <functional>
#include <queue>
#include <vector>
using namespace std;

//初始化
priority_queue<int,vector<int>,greater<int>>qu;
int n,x,sum,part;

int main(){
    //输入
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> x;
        qu.push(x);
    }
    //核心
    while(qu.size() >= 2){
        //合并最小的两个
        part = qu.top();
        qu.pop();
        part += qu.top();
        qu.pop();
        //计算体力总和
        sum += part;
        //合并
        qu.push(part);
    }
    //输出
    cout << sum;
    return 0;
}

时间复杂度是

O(n+(n-1))

//解析:输入为O(n),核心为O(n-1)