描述
一群n人希望用一条船过河，这条船最多只能载两个人。因此，必须安排某种穿梭安排，才能来回划船，以便所有人都能过关。每个人都有不同的划船速度；一对选手的速度取决于速度较慢的人的速度。你的工作是确定一个策略，尽量减少这些人的过河时间。
输入
输入的第一行包含一个整数t(186bc66ab0e65bd5ab105827278a7a575= 4 时，问题就复杂很多，因为任意两人过河，再在过了河中其中一个再回来有很多情况，我们这里需要进行分析
观察题目我们可以发现过河中有两个最为重要的点
方案【1】过河的两个人，花费时间是由最长的人决定
针对这一点，我们可以把最慢d的和次慢c的放一起，这样次慢的时间c就被忽略。
方案【2】回来的一个人，花费时间只由他一个人决定
针对这一点，我们可以让最快的a把其他人一一送过去，再由最快的a把船送回来
将上面的方案实现
当n = 4时（以下n人速度分别用abcd…表示，且按速度升序排序）（）内表示花费时间
方案【1】abcd
ab（b）过去
a （a）回来
cd（d）过去
b（b）回来
ab（b）过去
所花费时间：a+3b+d
方案【2】abcd
ad（d）过去
a（a）回来
ac（c）过去
a（a）回来
ab（b）过去
所花费时间：2a+b+c+d
计算样例
现在我们导入题目样例{1，2，5，10}
方案【1】时间 = 17
方案【2】时间 = 19
所以用方案【1】花费时间最短，时间为17
但如果我们修改一下数据{1，2，2，10}
方案【1】时间 = 17
方案【2】时间 = 16
这次却是方案【2】花费的时间最短，时间为16；
如果我们将两个方案的所花费时间约一下则
方案【1】：2b
方案【2】：a+c
可以看出所花费的时间 决定性因素 在于最快的a和次快的b和次慢的c，我们只需要将2b和a+c进行比较，选择花费时间最小的方案即可。
当n > 4 时我们可以表示为用最快的前两个人运送最慢的后两个人便可，运送完人数就减少2。
相关教程：java视频教程
下面是已经ac了的代码，仅供参考
import java.util.arrays;import java.util.scanner;public class 过河 { static long time = 0l; public static void main(string[] args) { scanner sc = new scanner(system.in); int m = sc.nextint(); for (int i = 0; i < m; i++) { int n = sc.nextint(); int[] a = new int[n]; for (int j = 0; j < n; j++) { a[j] = sc.nextint(); } arrays.sort(a); f(a); system.out.println(time); time = 0l; } } public static void f(int[] a) { if(a.length == 3) { time += a[0] + a[1] + a[2]; return; } if(a.length == 2) { time += a[1]; return; } if(a.length == 1) { time += a[0]; return; } if(a[0] + a[a.length - 2] < a[1] * 2) { time += 2 * a[0] + a[a.length - 2] + a[a.length - 1]; }else { time += a[0] + 2 * a[1] + a[a.length - 1]; } int[] b = arrays.copyofrange(a, 0, a.length - 2); f(b); }}
以上就是经典算法问题之过河详解的详细内容。