PTA 修理牧场（两种方法，注释详解）

2023-09-26 14:19| 来源: 网络整理| 查看: 265

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。

但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。

请编写程序帮助农夫计算将木头锯成N块的最少花费。

输入格式:

输入首先给出正整数N（≤10^4），表示要将木头锯成N块。第二行给出N个正整数（≤50），表示每段木块的长度。

输出格式:

输出一个整数，即将木头锯成N块的最少花费。

输入样例:

8 4 5 1 2 1 3 1 1

输出样例:

程序代码：

法一（定义优先队列）：

#include #include using namespace std; int main(){ int N,cost,sum,a; // 定义优先队列，小的在前面 priority_queue q; cin>>N; for(int i=0;i // 得到队列中最小的数 a=q.top(); // 出队 q.pop(); // 再取一个最小的数与前一个最小的数相加 a+=q.top(); // 出队 q.pop(); // 将前两个最小数相加的结果继续放入队列，循环 q.push(a); // 花费求和 sum+=a; } cout for(j=0;j t=a[i]; a[i]=a[j]; a[j]=t; } } } } int main() { int N,costsum=0,i,index; scanf("%d",&N); int *a=(int*)malloc(sizeof(int)*N); for(i=0;i // 前两个数的和大于当前值，继续往后找 if(sum>a[index]) a[index-1]=a[index]; else { // 不大于就找到位置，结束循环 a[index-1]=sum; break; } } // 比到最后一个数还没找到，就把sum加到最后 if(index==N) a[N-1]=sum; } printf("%d\n",costsum); return 0; }

本题主要采用构造最小生成树（哈夫曼树）的思想，每次找两个最小的子节点，构造父节点，最后输出根节点。以上两种方法都比较好理解，初学C语言的话，建议看一下第二种方法，理解一下算法思想，如果已经够熟练的话，采用第一种方法比较简单。供大家参考学习。

【本文地址】

公司简介

联系我们