运送马匹
有1个人,要把n匹马从A村运往B村。
初始时,人和马都在A村。每次骑1匹马牵1匹马,回来时骑1匹马。
已知每匹马从A村到B村需要的时间(数字越大越慢)
两匹马同行时只能迁就较慢者。
求所有马匹都运到B村的最小的运输时间(此时,人和马都在B村)。
程序首先输入一个整数n(n<100),表示有n匹马。
接着是n行整数,表示马从A村到B村的所用的分钟数(小于1000)
程序输出:1个整数,表示所有马匹均运到B村的最小总耗时。
例如,
输入:
3
1
2
4
程序应输出:
7
输入:
4
1
4
2
5
程序应该输出:
12
对于编程题目,要求选手给出的解答完全符合ANSI C++标准,不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。
代码中允许使用STL类库,但不能使用MFC或ATL等非ANSI c++标准的类库。例如,不能使用CString类型(属于MFC类库)。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意选择自己使用的编译环境。
思路:选择两匹最快的马匹来回运送其它的马匹,最后的最后再将这两批最快的马匹运回就完成了
因为用到贪心思想,所以一开始要将马匹的速度从小到大排序,得到速度最快的前两个马匹,之后
运用递归的方法来运送马匹,一回合用最快的马运送两个(例如:1,2,5,4,8:排序后:1,2,4,5,8;先用1,2,将1送到目的地,用时a[1],2返回
,用时a[1],之后速度倒数第二的马匹和速度倒数第一的马匹一起过去,用的时间是a[n-1](此时B地有马3匹,分别是1和a[n-2]和a[n-1]),
之后1再回去,用时a[0],一回合的用时就是a[1]*2+a[0]+a[n-1],此时运送了两匹马(a[n-2]和a[n-1])),直到运送完毕
#include<stdio.h> #include<algorithm> using namespace std; int a[200],sum=0; int Fun(int n) { if(n==1) sum+=a[0]; else if(n==2) sum+=a[1]; else if(n==3) sum+=a[1]+a[2]; else { sum+=2*a[1]+a[0]+a[n-1];//每一回合的式子 Fun(n-2);//运好两匹马之后递归 } } int main() { int i,j,n,m1,m2; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n);//排序(从小到大) Fun(n); printf("%d\n",sum); return 0; }