题目大意
给出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)
,每次是两个数相加而合并而成。