PTA 修理牧场（优先级队列）
发布时间
阅读量：
阅读量
题目描述：
农夫计划修复牧场的一段围栏。经过测量后确定所需木材数量为N块，并得知每根木材的长度均为整数值Lᵢ（单位：长度单位）。因此他决定购买一根足够长且可分割成N根所需木材的大木材。该大木材的实际总长度等于各部分木材长度之和。
然而农夫自己没有锯子 因此请人锯木时的酬金与所锯木头的长度成正比 为了简化计算 方便起见 假设酬金等于所 sawn wood 的长度 例如 有一根长20米 的木材需要被切成8米、7米 和5米三段 首先 将这根长20米 的木材第一次切割花费了20元 将其分为12米 和8米两部分 接着 对于长12米 的部分再次进行切割 花费了12元 切割出7米 和5米 两部分 这样两次切割总共花费了32元 如果在第一次切割时将木材分成15米 和5 米 则第二次切割花费了15元 总计费用则达到了35元（高于之前的情况）
请编写程序帮助农夫计算将木头锯成N块的最少花费。
输入格式:
随后输入包含一个自然数N（\leq 10^4），具体说明需要将木头分割成多少段）。接下来一行包含N个不超过50的正整数a_1, a_2, \dots, a_N，其中每个a_i代表一段木块的具体长度
输出格式:
输出一个整数，即将木头锯成N块的最少花费。
输入样例:
8
4 5 1 2 1 3 1 1输出样例:
49构建方法：自底向上的方式构造二叉树时的所有节点值总和即为最小成本。通过优先级队列可以模拟这个过程，请注意在给定输入样本的情况下这种方法能够有效地解决资源分配问题。
队列：5 4 3 2 1 1 1 1 sum = 0;然后
sum = 2 5 4 3 2 2 1 1
sum = 4 5 4 3 2 2 2
sum = 8 5 4 4 3 2
sum = 13 5 5 4 4
sum = 21 8 5 5
sum = 31 10 8
sum = 49 18 #include <bits/stdc++.h>
using namespace std;
//自定义优先级
struct ruel
{
bool operator()(const int a,const int b)
{
return a > b;
}
};
int main(){
priority_queue<int,vector<int>,ruel>p;
int num,a;
cin>>num;
for (int i=0;i<num;i++){
cin>>a;
p.push(a);
}
int sum=0;
while(p.size()!=1){
int x1=p.top();
p.pop();
int x2=p.top();
p.pop();
sum+=x1+x2;
p.push(x1+x2);
}
cout<<sum;
return 0;
}全部评论 (0)
还没有任何评论哟~