本篇文章的主要内容是关于经典算法问题之过河的详解，感兴趣的朋友可以了解一下，希望对你有所帮助。
描述
一群N人希望用一条船过河，这条船最多只能载两个人。因此，必须安排某种穿梭安排，才能来回划船，以便所有人都能过关。每个人都有不同的划船速度；一对选手的速度取决于速度较慢的人的速度。你的工作是确定一个策略，尽量减少这些人的过河时间。
输入
输入的第一行包含一个整数T(1<=T<=20)，测试用例数。接下来是T个案例。每个案例的第一行包含N，第二行包含N个整数，给出每个人过河的时间。每个案例前面都有一个空白行。不会有超过1000人，没有人需要超过100秒的跨越。
输出量
对于每个测试用例，打印一行，其中包含所有N个人过河所需的总秒数。
样本输入
1
4
1 2 5 10
样本输出
17
------------------------------------------------------------------------------------------------------------------------------
问题分析
（以下N人速度分别用abcd…表示，且按速度升序排序）
将上面的方案实现
当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);
}
}以上是经典算法问题之过河详解的详细内容。更多信息请关注PHP中文网其他相关文章！
