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

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

【算法思路】

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