【洛谷贪心算法】P1090合并果子

为了使消耗的体力最小，每次都应该选择当前重量最小的两堆果子进行合并。可以使用优先队列（小根堆）来实现这个过程，优先队列可以自动维护元素的顺序，每次取出堆顶的两个元素（即最小的两个元素）进行合并，然后将合并后的结果重新插入堆中，重复这个过程直到堆中只剩下一个元素。

【算法思路】

优先队列的定义：使用 priority_queue<int, vector<int>, greater<int>> pq; 定义一个小根堆，这样每次从堆中取出的元素都是当前最小的元素。读入数据：通过循环读入每堆果子的重量，并将其加入优先队列。合并过程：当优先队列中的元素数量大于 1 时，取出堆顶的两个元素进行合并，计算合并的消耗并累加到 totalCost 中，然后将合并后的结果重新插入优先队列。输出结果：当优先队列中只剩下一个元素时，合并过程结束，输出 totalCost，即最小的体力消耗值。

【代码示例】

#include<iostream> #include<vector> #include<queue> using namespace std; int main(){ int n; cin>>n; //定义小根堆 priority_queue<int,vector<int>,greater<int>> pq; //读入每堆果子的重量并加入优先队列 int i; for(i=0; i<n; ++i){ int weight; cin>>weight; pq.push(weight); } int totalCost = 0; //当堆中元素数量大于1时，继续合并 while(pq.size() > 1){ //取出最小的两堆果子 int a = pq.top();//获取不移除 pq.pop();//移除 int b = pq.top(); pq.pop(); //计算合并这两堆果子的消耗 int cost = a+b; totalCost += cost; //将合并后的果子堆加入优先队列 pq.push(cost); } //输出最小的体力消耗值 cout<<totalCost<<endl; return 0; }