公司建站文案给网站公司看的,网站域名备案系统,个人网站可以注册com域名吗,外贸建站网站公司为了使消耗的体力最小#xff0c;每次都应该选择当前重量最小的两堆果子进行合并。可以使用优先队列#xff08;小根堆#xff09;来实现这个过程#xff0c;优先队列可以自动维护元素的顺序#xff0c;每次取出堆顶的两个元素#xff08;即最小的两个元素#xff09;进…
为了使消耗的体力最小每次都应该选择当前重量最小的两堆果子进行合并。可以使用优先队列小根堆来实现这个过程优先队列可以自动维护元素的顺序每次取出堆顶的两个元素即最小的两个元素进行合并然后将合并后的结果重新插入堆中重复这个过程直到堆中只剩下一个元素。
【算法思路】
优先队列的定义使用 priority_queueint, vectorint, greaterint pq; 定义一个小根堆这样每次从堆中取出的元素都是当前最小的元素。读入数据通过循环读入每堆果子的重量并将其加入优先队列。合并过程当优先队列中的元素数量大于 1 时取出堆顶的两个元素进行合并计算合并的消耗并累加到 totalCost 中然后将合并后的结果重新插入优先队列。输出结果当优先队列中只剩下一个元素时合并过程结束输出 totalCost即最小的体力消耗值。
【代码示例】
#includeiostream
#includevector
#includequeue
using namespace std;int main(){int n;cinn;//定义小根堆 priority_queueint,vectorint,greaterint pq;//读入每堆果子的重量并加入优先队列 int i;for(i0; in; i){int weight;cinweight;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 ab; totalCost cost;//将合并后的果子堆加入优先队列 pq.push(cost);} //输出最小的体力消耗值 couttotalCostendl;return 0;
}
