P1090-合并果子 - 从萌新到萌新的成长历程

题目传送门

题目思路

本质上就是个贪心，每次都选两个最小的就可以了。

大坑：是每次选两个最小的，而不是从原始序列选，草，第一次就被坑了

补一点优先队列：

定义：priority_queue<Type, Container, Functional>
//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

AC代码

#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    priority_queue<int, vector<int>, greater<int>> a;
    for (int i = 0; i < n; i++)
    {
        int temp;
        scanf("%d", &temp);
        a.push(temp);
    }
    int sum = 0;
    for (int i = 0; i < n - 1; i++)
    {
        int temp1 = a.top();
        a.pop();
        int temp2 = a.top();
        a.pop();
        sum += temp1 + temp2;
        a.push(temp1 + temp2);
    }
    printf("%d", sum);
    return 0;
}