修理牧场（哈夫曼树）
发布时间
阅读量：
阅读量
7-1 维护牧场（25 分）
农夫计划修复牧场的一段围栏，并进行了详细测量以确定所需材料的数量与规格。他计算出总共需要N块木材，并确定每一块木材的标准长度为整数L_i个单位长度。随后他采购了一根足够长并可切割成指定数量木材的大木材料板；其总长度等于所有L_i之总和。
但是农夫自己没有工具，请人切割木材时所付报酬与其所切割木材的长度呈正比。为了便于理解，在举例时假设酬金即等于被切割木材段落的实际长度。例如要将一根长为20米（或其他单位）的木材分割成8米、7米和5米三段，则应首先进行一次成本较高的切割操作：第一次切割耗费的时间或费用（这里用数值表示）是20单位，并将其分成12米和8米两段；随后再对剩下的12米木材进行第二次切割：耗费时间或费用是12单位，并将其切成7米和5米两段；总费用即为此两项之和：32单位。如果他第一次就切下15米和5米两段，则第二次切割耗费的时间或费用是15单位……总费用则达到35单位（超过之前的最低成本32单位）。
请编写程序帮助农夫计算将木头锯成N块的最少花费。
输入格式:
首先包含一个不超过10^4的正整数N，在线性时间内计算出满足条件的结果值并将其返回。随后包含一行由不超过50的正整数组成的内容。
输出格式:
最终结果是一个非负整数值。
输入样例:
8
4 5 1 2 1 3 1 1
输出样例:
49
根据题意可知，求最少花费即为构造哈夫曼树的过程。
代码如下：
#include<iostream>
#include<vector>
using namespace std;
void Sum(vector<int> &arr)
{
int total=0;//总花费
while(arr.size()>1)
{
int min1=arr[0];//权值最小的两个值
int pos1=0,pos2=0;//当前最小结点的下标
int tmp=0;//保存当前两个最小结点的权值之和
for(int i=1; i<arr.size(); i++)
{
if(arr[i]<min1)
{
min1=arr[i];
pos1=i;
}
}
tmp+=min1;
arr.erase(arr.begin()+pos1);
int min2=arr[0];//删除一个数之后的第一个元素
for(int i=1; i<arr.size(); i++)
{
if(arr[i]<min2)
{
min2=arr[i];
pos2=i;
}
}
tmp+=min2;
arr.erase(arr.begin()+pos2);
total+=tmp;
arr.push_back(tmp);
}
cout<<total;
}
int main()
{
int N,W;
cin>>N;
vector<int> weight;
for(int i=0; i<N; i++)
{
cin>>W;
weight.push_back(W);
}
Sum(weight);
return 0;
}全部评论 (0)
还没有任何评论哟~