2025年经典小船过河问题，附Python，java题解

大家好，我是讯享网，很高兴认识大家。

同学在面试时遇到了一个有趣的编程题，笔者很有兴趣，故以此文章作为记录。

题目：

N个人过河，船每次只能坐两个人，船载每个人过河的所需时间不同t[i]，每次过河的时间为船上的人的较慢的那个，问最快的过河时间。(船划过去要有一个人划回来)。

首先分析下场景，我们首先要考虑的是如何把耗时最长的人送过去，而题目中明确说明了每次计时都要以较慢的记，我们很容易想到，让最慢的两个人一起过，是比较好的策略。展开分析，发现可能的情况有两种。

情况1：让最快的两个人和最慢的两个人组成一组，我们按照耗时长短分为a,b,c,d。要把cd送到对面，总共分4步(其中ab回对岸，是为了接其他剩下的人过河，因为他们是耗时最短的两个人)：

第一步：a,b过河 ------ 耗时 b

第二步：a留在对岸，b回去 ------ 耗时 b

第三步：c，d过河 ------ 耗时 d

第四步：a开船回来 ------ 耗时 a

总耗时为：a + 2 * b + d

但我们发现，其中b是需要计算两次的，这时如果四个值分别为 1,2,9,10，使用这种策略的耗时为：1 + 2*2+10 = 15；

如果四个值分别为 1,8,9,10，使用这种策略的耗时为：1 + 8*2+10 = 27；显然这种情况当b耗时较大的时候不是最优策略，我们如果使用下面的策略，耗时会更短。

情况2：让最快的人带耗时最久的两个人过河，即把4人一组改为3人一组，我们按照耗时长短分为a,c,d。要把cd送到对面，总共分4步(同理，其中a回对岸，是为了接其他剩下的人过河，因为他是耗时最短的人)：

第一步：a,c过河 ------ 耗时为c

第二步：a 回来 ------ 耗时为a

讯享网

第三步：a，d过河 ------ 耗时为 d

第四步：a回来 ------ 耗时为a

总耗时为 : a *2 + c + d

这种策略下，刚才的情况: 如果四个值分别为 1,8,9,10的耗时为 1 * 2 + 9 + 10 = 21 < 27, 比策略1优。

我们知道了这两种策略，就不难根据两种策略写出代码：

思路为：首先排序，得到耗时由小到大的数组，然后每次判断两种策略哪种更优，把总时间累加即可。

需要考虑边界条件：当数组剩余长度为3时，此时的耗时为 a + b + c（此时a不需要再回对岸接其他人了，已经没有其他人了）；

当数组剩余长度为2：耗时为 b，因为他是两个人中耗时较长的。

这样，整个流程就结束了。

Python代码示例:

# -*- coding: utf-8 -*- def bridge(times): times.sort() n = len(times) ret = 0 while n > 3: #策略1 t1 = times[0] + 2 * times[1] + times[n - 1] #策略2 t2 = times[0] * 2 + times[n - 1] + times[n - 2] temp = t1 if t1 < t2 else t2 ret += temp #当前未过河的耗时最长的两个人已经过河，所以要减2 n -= 2 #特殊情况，剩3个人时，耗时最短的已经不用回来了，直接留在对岸 if n == 3: t = times[0] + times[1] + times[2] ret += t return ret #特殊情况，取耗时较长的 if n == 2: t = times[1] ret += t return ret times = [2,10,12,11] times = [2,7,3,8] print bridge(times)

讯享网

java代码示例:

讯享网import java.util.Arrays; public class Bridge { / * 过桥问题. */ public static int bridge(int[] times) { Arrays.sort(times); int result = 0; int leftNum = times.length; while (leftNum > 3) { int cost1 = times[0] + 2 * times[1] + times[leftNum - 1]; int cost2 = times[0] * 2 + times[leftNum - 1] + times[leftNum - 2]; int temp = cost1 < cost2 ? cost1 : cost2; result += temp; leftNum -= 2; } if (leftNum == 3) { result += times[0] + times[1] + times[2]; return result; } if (leftNum == 2) { result += times[1]; } return result; } public static void main(String[] args) { int[] times = {2, 7, 3, 8}; System.out.println(Bridge.bridge(times)); } }

启发：遇到问题是先思考有哪些情况，有哪些策略，然后将问题拆解为处理的最小单元。

以上代码仅为参考，由于笔者水平有限，难免有理解不当之处，欢迎大家批评指正。

2025年经典小船过河问题，附Python，java题解

相关推荐