| input | output |
|---|---|
4 1 10 5 2 |
17 |
题目：有n个人在雷区的左边。他们各自有自己跨越雷区的所需时间。他们只有一个扫雷器。为了能安全通过，他们只能两个人或者一个人带着扫雷器在雷区里走。两个人走过雷区的时间，以时间长的算。因为只有一个扫雷器，如果左边还有人，右边的人还要把扫雷器送回到左边。
注意开始只有两个人的时候的特判。
走法：当人数大于不等于四个人的时候。 有两种走法。 挑出 走的最快的a，第二快的b。然后再从 最慢的 z，和第二慢的 y开始。 原则 是a，b来送z和y过去，但是a，b 要回到左边。这里有两种走法，一种只用到a， a和z一起过去，再a一个人回来，再a和y一起过去，再a回来。耗时是a*2+y+z。 第二种走法是，a和b过去，a一个人回来，y和z一起过去，b一个人把扫雷器带回来。 耗时是 b*2+a+z。
再计算 三个人和四个人的情况就好了。见代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#include <vector>
int main()
{
int n;
int arr[110];
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
cin>>arr[i];
sort(arr,arr+n);
if(n==2)
{
cout<<arr[1]<<endl;
continue;
}
int j=n-1;
int ans=0;
for(;j>=4;j-=2)
{
ans+=min(arr[0]*2+arr[j]+arr[j-1],arr[0]+arr[1]*2+arr[j]);//四个人以上的情况
}
if(n&1)
ans+=arr[0]+arr[j]+arr[j-1];//最后三个人
else
ans+=min(arr[0]*2+arr[1]+arr[j]+arr[j-1],arr[0]+arr[1]*3+arr[j]);//最后四个人
cout<<ans<<endl;
}
return 0;
}
原文：http://blog.csdn.net/u013532224/article/details/44280349