合并果子(STL)
这是一道比较经典的贪心算法题目,洛谷 P1090《合并果子》。
这是一道比较经典的贪心算法题目,洛谷 P1090《合并果子》。
题目要求将若干堆果子合并成一堆,每次只能合并两堆,消耗的体力等于这两堆果子的重量之和,求全部合并完成后消耗的最小体力。
一、题目分析
假设有 $n$ 堆果子,每堆果子的数量分别为 $a_1,a_2,\ldots,a_n$。
每次选择两堆进行合并,合并后的新堆还需要参与后面的合并,因此一共需要进行 $n-1$ 次操作。
例如有三堆果子:
1 2 9
如果先合并1和2,消耗体力为3,剩下:
3 9
再将3和9合并,消耗体力为12。
总共消耗:
但如果先合并2和9,就需要消耗11,剩下1和11,再合并需要12,总共消耗23。
所以合并的顺序会直接影响最终结果。
由于每次合并得到的新堆还需要继续参与后面的计算,如果一开始就把比较大的两堆合并,那么后续可能还需要反复计算这部分重量,造成更多的体力消耗。
因此可以采用贪心策略:每次选择当前最小的两堆果子进行合并,再把新堆放回去,继续选择最小的两堆。
重复以上操作,直到只剩下一堆。
二、优先队列
如果直接使用数组存储,每次都要找出最小的两个数,合并以后还需要重新寻找。
这里可以使用 STL 中的优先队列 priority_queue。
普通优先队列默认是大根堆,每次取得的是最大的元素。
而这道题需要每次取出最小的两个元素,所以需要使用小根堆:
priority_queue <int, vector <int>, greater <int> > R;
其中:
int表示存储的数据类型。vector<int>表示底层容器。greater<int>表示按照从小到大的优先级取出元素,使队首为最小值。
优先队列主要使用以下几个操作:
R.push(x);
向队列中插入一个元素。
R.top();
取得当前最小的元素。
R.pop();
删除队首元素。
R.size();
取得队列中的元素数量。
这样就不需要每次手动对数组重新排序。
三、代码实现
#include <iostream>
#include <queue>
using namespace std;
int main()
{
int n,result = 0;
priority_queue <int, vector <int>, greater <int> > R;
cin >> n;
for (int i = 1; i <= n; i++)
{
int a;
cin >> a;
R.push(a);
}
while (R.size() >= 2)
{
int x = R.top();
R.pop();
int y = R.top();
R.pop();
result += x + y;
R.push(x + y);
}
cout << result << endl;
return 0;
}
四、代码分析
首先读入果子的堆数 n,再将所有果子的数量依次加入优先队列。
for (int i = 1; i <= n; i++)
{
int a;
cin >> a;
R.push(a);
}
由于使用的是小根堆,所以队首始终是当前最小的元素。
接着使用:
while (R.size() >= 2)
判断当前是否还存在至少两堆果子。
每次从优先队列中取出两个最小值:
int x = R.top();
R.pop();
int y = R.top();
R.pop();
将这两堆合并,并累加本次消耗的体力:
result += x + y;
最后将合并后的新堆重新加入优先队列:
R.push(x + y);
因为新堆也需要参与后面的合并,所以必须重新插入。
当队列中只剩下一个元素时,说明所有果子已经合并完成,输出 result 即可。
五、复杂度分析
优先队列采用堆结构,每次插入和删除元素的时间复杂度为 $O(\log n)$。
首先需要将 $n$ 堆果子全部插入优先队列。
之后一共进行 $n-1$ 次合并,每次合并需要两次取出和一次插入操作。
因此总时间复杂度为:
优先队列最多保存 $n$ 个元素,空间复杂度为:
相比每次都重新排序的方法,使用优先队列可以减少大量不必要的操作。
六、总结
这道题主要使用了贪心算法和 STL 优先队列。
贪心的关键是每次都选择最小的两堆进行合并,使较大的果子堆尽量减少重复参与合并的次数。
使用 priority_queue 可以方便地维护当前最小的元素,不需要手动排序。
这种反复选择两个最小元素再合并的思想,也与 Huffman 树的构造过程相同。
对于这道题,只需要维护一个小根堆,每次取出两个最小值,累加后重新插入,直到队列只剩下一个元素即可。

















这一切,似未曾拥有