5375: 【J1】【优先队列】修理牧场
发布时间
阅读量：
阅读量
题目描述
农夫需要修理牧场的一段栅栏。他测量了栅栏的长度后发现总共需要N块木材，并计算得知每根木材的长度均为整数值Li。为了满足需求农夫购买了一根足够长且可分割成N根所需木材的大木材
但是农夫自己并没有准备好所需的工具，请人代为完成这项工作时所需支付的工作报酬与其所加工木材长度之间呈正比关系。为了便于理解问题的本质，在此不妨假设工作报酬即等于所加工木材长度数值本身。举个例子来说，在将一根长为20米的木材分割成长分别为8米、7米及5米的三段时：首先进行第一次切割操作需投入成本费用共计20元人民币，并将其分切成一段长为12米与另一段长为8米的小木材；随后再次进行切割操作投入成本费用共计12元人民币，并将其分切成长分别为7米及5米的小木材两根。经计算可知总共投入的成本费用合计34元人民币（包括两次切割操作）。然而假如在第一次切割过程中就直接分切成长分别为15米与5米的小木材，则后续第二次切割所需要投入的成本费用则会增加至共计34元人民币（包括两次切割操作），这显然高于之前所述的第一种情况下的总成本费用支出水平（共计34元人民币）。
请帮农夫计算将木头锯成N块的最大花费和最小花费。
输入
为了更好地明确切割方案，请确定一个正整数N（不大于104），具体说明需要将木头切割成多少块。然后，请提供一组不超过50的正整数序列,这些数值将分别对应每一块切割后的木块长度.
输出
2个整数，即将木头锯成N块的最大花费和最小花费。
样例输入
样例输出
Code:
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q1;
priority_queue<int,vector<int> >q2;
int n,x,ans1,ans2;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
q1.push(x);
q2.push(x);
}
while(q1.size()>=2){
int a=q1.top();
q1.pop();
int b=q1.top();
q1.pop();
ans1+=a+b;
q1.push(a+b);
}
while(q2.size()>=2){
int a=q2.top();
q2.pop();
int b=q2.top();
q2.pop();
ans2+=a+b;
q2.push(a+b);
}
cout<<ans2<<" "<<ans1;
return 0;
}全部评论 (0)
还没有任何评论哟~