7-8（树）修理牧场 (25分)

最新推荐文章于 2021-07-29 14:59:56 发布

寻寻寻寻

最新推荐文章于 2021-07-29 14:59:56 发布

阅读量297

点赞数

分类专栏：原创编程题AC代码文章标签：算法

本文链接：https://blog.csdn.net/SDU_st/article/details/109709027

版权

原创编程题AC代码专栏收录该内容

14 篇文章

订阅专栏

这篇博客介绍了农夫如何通过优化锯木头的方式，以最小的花费将一条长木头锯成指定长度的N块。问题涉及到算法优化，通过实例解释了如何计算锯木头的最小成本，以解决实际问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

7-8（树）修理牧场 (25分)

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

但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为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

输出样例:

AC代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int mincho(int ar[],int n) {
	int n1=59999991,n2=5999991;
	int p1=-1,p2=-1;
	for(int i=0; i<n; i++) {
		if(ar[i]<n1) {
			n1=ar[i];
			p1=i;
		}
	}
	for(int i=0; i<n; i++) {
		if(i==p1)continue;
		if(ar[i]<n2) {
			n2=ar[i];
			p2=i;
		}
	}
	if(p1==n-1&&p2<n-2)ar[p2]=ar[n-2];
	else if(p1==n-2&&p2<n-2)ar[p2]=ar[n-1];
	else if(p2==n-1&&p1<n-2)ar[p1]=ar[n-2];
	else if(p2==n-2&&p1<n-2)ar[p1]=ar[n-1];
	else {
		ar[p1]=ar[n-1];
		ar[p2]=ar[n-2];
	}
	return n1+n2;
}
int main() {
	int n;
	scanf("%d",&n);
	int ar[n];
	for(int i=0; i<n; i++) {
		scanf("%d",&ar[i]);
	}
	int allcost=0;
	while(n!=1) {
		int point=mincho(ar,n);

		allcost+=point;
		ar[n-2]=point;
		n--;
//		for(int i=0;i<n;i++){
//			printf("%d ",ar[i]);
//		}
		//	putchar('\n');
	}
	cout<<allcost<<endl;

	return 0;
}