英文题目：
A group of N people wishes to go across a river with only one boat, which can at most carry two persons. Therefore some sort of shuttle arrangement must be arranged in order to row the boat back and forth so that all people may cross. Each person has a different rowing speed; the speed of a couple is determined by the speed of the slower one. Your job is to determine a strategy that minimizes the time for these people to get across.
1 4 1 2 5 10
17
----------------------------------------------------------------------------------------------------------------------------------------------
中文描述：就是有一条河，只有一条船，有n个人，每个人有自己的过河时间，一条船只能载两个人，过河时间算两个人中最大时间那个。算出最少过河时间。
个人理解：首先我做这道题题目时候，这个题目使用贪心策略；
首先我们来分析四个人的情况，因为3、2、1个人的时候很好办；首先有a（最快）、b（次快）、c（次慢）、d（最慢），分两个策略来解决问题。
1.a和b过河，a回来（保证时间最少），c和d过河，b回去（保证时间最少），保证下一次运输时候，a和b来作为来回运输的人，保证时间最少。
2.a和d过河，a回来，a和c过去，a回来。
所以我们只要在n>3个人的时候来比较这两个策略那一个策略时间比较少，然后n-2；直到人数剩下3人一下（包括3个人）。
我们来代码实现：
1 #include<stdio.h> 2 #include<algorithm> 3 #include<math.h> 4 #include<vector> 5 #include<iterator> 6 #include<string> 7 #include<string.h> 8 #include<ctype.h> 9 #include<map> 10 #include<stack> 11 #include<queue> 12 #include<iostream> 13 #include<time.h> 14 15 using namespace std; 16 17 #define rep(i ,a, b) for(int i = a; i <= b; i++) 18 #define per(i, a, b) for(int i = a; i <= b; i--) 19 int a[1005]; 20 21 int main() 22 { 23 int t, n, sum;//最简单的基础贪心问题； 24 scanf("%d", &t);//过河有两种策略； 25 while(t--) 26 { 27 n = 0; 28 sum = 0; 29 scanf("%d", &n); 30 for(int i = 0; i < n; i++) 31 { 32 scanf("%d", &a[i]); 33 } 34 sort(a, a+n); 35 while(n > 3) 36 { 37 sum = min(sum+a[1]+a[0]+a[n-1]+a[1],sum+a[n-1]+a[0]+a[n-2]+a[0]); 38 n-=2;//保证人数过去时时间最大的两个人。 39 } 40 if(n == 3) 41 { 42 sum += a[0]+a[1]+a[2]; 43 } 44 if(n==2) 45 { 46 sum +=a[1]; 47 } 48 if(n==1) 49 { 50 sum += a[0]; 51 } 52 printf("%d\n", sum); 53 } 54 return 0; 55 }
原文：https://www.cnblogs.com/chinwongleung/p/9822275.html
