1009
2013藍橋杯【模擬賽】運送馬匹
運送馬匹
有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;
}
最後更新：2017-04-03 12:55:36