青藤 #136 合并果子

题目大意

给出n个数,每次将两个数合起来,消耗两个数的和的体力,输出最少的体力。

思路

priority_queue 即可。

因为要使体力最小,所以要从小到大排。但 priority_queue 是从大到小……

用负数!

#include <bits/stdc++.h>
using namespace std;
int n;
priority_queue<int> m;
int main() {
    long long n, ans = 0;
    int t;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t;
        m.push(-t);
    }
    while (m.size() != 1) {
        int p = 0;
        ans += m.top(), p += m.top(), m.pop();
        ans += m.top(), p += m.top(), m.pop();
        m.push(p);
    }
    cout << -ans;
    return 0;
}

温馨提醒:第17行请不要写成m.push(ans),每次是两个数相加而合并而成。

上一篇:优先队列


下一篇:TD 多线程