洛谷题单指南-贪心-P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

原题链接：https://www.luogu.com.cn/problem/P1090

题意解读：两两合并，是典型的哈夫曼编码算法思想，贪心即可。

解题思路：

要是合并体力消耗最少，就要让尽可能少的果子越晚合并越好，

因此，贪心策略为优先选择数量最少的两堆果子合并，一直到剩下一堆果子，把合并过程中的消耗值累加即可，

要快速选择最小的两个数，可以借助于优先队列。

100分代码：

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

const int N = 10005;

priority_queue<int, vector<int>, greater<int> > q;
int n, ans;

int main()
{
    cin >> n;
    int x;
    for(int i = 1; i <= n; i++) cin >> x, q.push(x);

    while(q.size() >= 2)
    {
        int a = q.top(); q.pop();
        int b = q.top(); q.pop();
        int sum = a + b;
        q.push(sum);
        ans += sum;
    }
    
    cout << ans;

    return 0;
}