Crossing River

题目链接： http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=26251

题意：

N个人希望去过河，但每次只能过两个且要有一个人把船划回来接其他的人；

两个人一起过河所用的时间是两个人中单独过河时间最多的；

求所有人过河所需要的最少的时间。

思路分析：

定义一个装n个人中每个人过河所需要的时间数组a[]；并用sort进行从小到大进行排序。

求将最慢的和次慢的运过去所需的最少时间，下面有两种可能使所需时间最短的运送的方法：

1）先让最快的和次快的过去且让最快的回来，后要最慢的和次慢的过去让次快的回来；

这样所需要的时间为a[0]+2*a[1]+a[n-1]

2）让最慢的和最快的过去最快的回来；再让最快的和次慢的过去最快的回来；

这样所需要的时间为2*a[0]+a[n-1]+a[n-2]

将这两种方法所需的时间进行比较。

说明：当只有3个人或更少时不管如何过河所需的时间都是他们单独过河所需的时间的总和。

 1 #include<iostream>
 2 #include<algorithm>
 3   using namespace std;
 4   const int maxn=1000;
 5 int main()
 6 {
 7     int i,j,t,n,sum,a[maxn];
 8      cin>>t;
 9 while(t--)
10 {
11     j=0;sum=0;
12     cin>>n;
13 for(i=0;i<n;i++)
14       cin>>a[i];
15   sort(a,a+n);
16 for(i=n-1;i>2;i-=2)
17       if(a[0]+2*a[1]+a[i]<2*a[0]+a[i]+a[i-1])
18               sum=sum+a[0]+2*a[1]+a[i];
19           else
20               sum+=2*a[0]+a[i]+a[i-1];
21      if(i==2)
22             sum=sum+a[1]+a[0]+a[2];
23     if(i==1)
24              sum=sum+a[1];
25    if(i==0)
26            sum+=a[0];
27 cout<<sum<<endl;
28 }
29 return 0;
30 }

View Code