研0 冲刺算法竞赛 day27 P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
考点:哈夫曼树
思路:建优先队列,自动排序,然后每次取出最小两个即可。本来思路是数组的,但是一直写不对,可能是情况想少了
代码:
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;priority_queue<int, vector<int>, greater<int>> q;//优先队列int n, x, ans;int main()
{cin >> n;for (int i = 0; i < n; ++i){cin >> x;q.push(x);//插入x}while (q.size() >= 2) {//只剩一个结束int a = q.top(); q.pop();int b = q.top(); q.pop();//弹出最小的两个ans += a + b;q.push(a + b);}cout << ans << endl;return 0;
}
总结:优先队列,作为最小堆使用