过河问题算法时间最短,农夫过河算法
本文的主要内容是关于经典算法问题的详细解释。感兴趣的朋友可以了解一下，希望对你有帮助。
描述
一群N人要坐船过河，最多只能载两个人。所以一定要安排某种穿梭排列，才能来回排，才能让大家过关。每个人的划船速度都不一样；一对选手的速度取决于较慢者的速度。你的工作是确定一个策略来最小化这些人的穿越时间。输入
输入的第一行包含一个整数T(1=T=20)，测试用例的数量。接下来是测试案例。每个案例的第一行包含n，第二行包含n个整数，给出大家过河的时间。每个案例前面都有一个空行。不会超过1000人，也没有人需要超过100秒才能穿越。
输出
对于每个测试案例，打印一行所有N个人过河所需的总秒数。样本输入
一个
四
1 2 5 10样本输出
17
------------------------------------------------------------------------------------------------------------------------------
问题分析
(以下N人速度分别用abcd…表示，按速度升序排序)
当n=1时，时间是A，当n=2时，时间是b，当n=3时，时间是a b c(a和任意一个人过河，A回来，然后和剩下的人一起过河)。当n=4时，问题就复杂多了，因为任意两个人过河，然后其中一个人过河后又回来的情况很多，这里需要分析一下。
观察题目可以发现，过河有两个最重要的点。
方案【1】两个人过河，用的时间由最长的人决定。
鉴于此，我们可以把最慢的D和第二慢的C放在一起，这样第二慢的C就被忽略了。
方案【2】回来的人所花的时间只由他自己决定。
鉴于此，我们可以让最快的A把其他的一个一个送过去，然后最快的A把船送回将上面的方案实现当n = 4时(下面N个人的速度分别用abcd…表示，按速度升序排序) ()表示花费的时间。
方案[1] ABCD
过去的
回来
Cd(d)过去
回来吧。
Ab(b)过去所花费时间: A3BD
方案二ABCD
过去的事
回来
Ac(c)过去
回来
Ab(b)过去所花费时间:2a b c d
计算样例
现在让我们导入示例问题{1，2，5，10}
方案[1]时间=17
方案[2]时间=19
所以方案[1]耗时最短，为17。
但是如果我们修改数据{1，2，2，10}
方案[1]时间=17
方案二时间=16
然而这一次，方案[2]耗时最短，为16；
如果我们估算两种方案所花费的时间，那么
方案[1]: 2b
方案[2]: a c
可以看出决定性因素花费的时间在于最快的A，第二快的B，第二慢的c，我们只需要比较2b和a c，选择花费时间最少的方案。
当n 4 时我们可以表示最快的前两个人可以运送最慢的后两个人，运送后人数会减少2。
相关教程：Java视频教程
以下是AC代码，仅供参考。
导入Java . util . arrays；
导入Java . util . scanner；
公共课过江
{
静态长时间=0L
公共静态void main(String[] args)
{
Scanner sc=新扫描仪(system . in)；
int m=sc . nextint()；
for(int I=0；我是m；我)
{
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)；
时间=0L
}
}
公共静态void f(int[] A) {
if(A.length==3) {
时间=A[0]A[1]A[2]；
返回；
}
if(A.length==2) {
时间=A[1]；
返回；
}
if(A.length==1) {
时间=A[0]；
返回；
}
if(A[0] A[A.length - 2] A[1] * 2) {
时间=2 * A[0]A[A . length-2]A[A . length-1]；
}否则{
时间=A[0]2 * A[1]A[A . length-1]；
}
int[]B=arrays . copyofrage(A，0，A . length-2)；
f(B)项；
}
}以上是经典算法问题详解的详细内容。更多请关注我们的其他相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。