信息课总结（一）

贪心与排序

一、合并果子（洛谷ojP1090）

原题是洛谷的P1090 合并果子
思路：要使总共的和最小，则要使单次总和最小，那么只要每次都取最小的两堆进行合并即可，即每次要进行排序，将整个负责保存每堆数量的容器从小到大排。
实现：这道题应用了优先队列(priority_queue)，利用了优先队列将所有数从大到小进行排列的这种优势，直接得到大小序列，但是为了将小的放在前面好pop掉，所以保存的时候要先将push进去的那个数取反（取相反数），在使用的时候再改为正的。

//#include <bits/stdc++.h>
#include <cstdio>
#include <queue>
#include <iostream>

using namespace std;

int main()
{
    int kinds;
    cin >> kinds;
    priority_queue<long long> a;
    for (int i = 0; i < kinds; i++) {
        int p;
        scanf("%d", &p);
        a.push(-p);
    }
    long long tot = 0;
    while (a.size() >= 2) {
        long long r = -a.top();
        a.pop();
        long long s = -a.top();
        a.push(-r-s);
        a.pop();
        tot+=(r+s);
    }
    printf("%lld\n", tot);
    return 0;
}