PTA 数据结构与算法 7-29 修理牧场
发布时间
阅读量：
阅读量
正式开始
请编写程序帮助农夫计算将木头锯成N块的最少花费。
输入首先呈现一个不超过10^4的正整数N。第二行呈现N个不超过50的正整数。
输出格式:
输出一个整数，即将木头锯成N块的最少花费。
输入样例:
8
4 5 1 2 1 3 1 1
输出样例:
49
这道题目与POJ中的一道典型编程题极为相似，在《算法竞赛入门经典》一书中也提供了详细解析。让我来深入探讨一下这个问题。
我们可以将一根木头视为一棵树的基本结构模型。每一次切割实际上等价于将该木头分割为两个独立的部分（子结构），而每个子结构所对应的权值即代表被分割出的那一段木头的实际长度。
我们的目标则是构造这样一棵具有最小总权重（即最低切割成本）的标准形式——Hoffman树。
而这就是Hoffman编码算法的核心思想：通过合理分配各字符出现频率（权重），使得最终生成的理想编码方案达到最低平均码长。
因此我们的问题转化为寻找能够实现最低成本的一棵Hoffman编码结构。
为了更好地理解这一概念，请参考以下示例图。
代码：
#include<stdio.h>
#define swap(a,b) a=a^b,b=a^b,a=a^b
int tail=0; //堆的最后一个元素的下一个位置
void Insert(int *length,int temp);
int GetHeap(int *length);
int Solve(int *length);
int main(void)
{
int N;
int i;
scanf("%d",&N);
int length[N];
int temp;
for(i=0;i<N;i++){
scanf("%d",&temp);
Insert(length,temp); //构造一个小顶堆
}
printf("%d",Solve(length));
return 0;
}
void Insert(int *length,int temp)
{
int son,father;
son=tail;
length[tail++]=temp;
father=(son+(son&1))/2-1;
if(!son)
return ;
while(length[son]<length[father]&&father>=0){
swap(length[son],length[father]); //交换两节点位置
son=father;
father=(father+(father&1))/2-1;
}
return ;
}
int GetHeap(int *length)
{
int result=length[0];
int father=0;
int son=1;
length[0]=length[--tail];
while(son<tail){
if(length[son]>length[son+1])
son++; //如果左孩子节点的数值更大
if(length[father]>length[son]){
swap(length[father],length[son]);
father=son;
son=2*son+1;
}
else
break;
}
return result;
}
int Solve(int *length)
{
int min1,min2;
int result=0;
if(tail==1)
return 0;
while(1!=tail){
min1=GetHeap(length);
min2=GetHeap(length); //找打最小的两块板子
result+=min1+min2; //将其合为一块板子
Insert(length,min1+min2); //继续排序
}
return result;
}测试结果：
全部评论 (0)
还没有任何评论哟~