1 条题解
-
0
【本题解由站长编写】
经典小根堆模拟:每次取出最小的两个数,把它们的和计入答案,再把和压回堆中,直到只剩一个数。所有费用之和就是答案,注意用 long long。
代码(C++17)
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; priority_queue<long long, vector<long long>, greater<long long>> q; for (int i = 0; i < n; i++) { long long x; cin >> x; q.push(x); } long long cost = 0; while (q.size() > 1) { long long a = q.top(); q.pop(); long long b = q.top(); q.pop(); cost += a + b; q.push(a + b); } cout << cost << endl; return 0; }
- 1
信息
- ID
- 4074
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者