java中经典算法问题之过河的案例?这个问题可能是我们日常学习或工作经常见到的。希望通过这个问题能让你收获颇深。下面是小编给大家带来的参考内容,让我们一起来看看吧!
描述
一群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。
下面是已经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); } }
感谢各位的阅读!看完上述内容,你们对java中经典算法问题之过河的案例大概了解了吗?希望文章内容对大家有所帮助。如果想了解更多相关文章内容,欢迎关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。