我要招人

去企业版

首页 > 试题广场 >

有ABCD四个人要在夜里过一座桥，他们通过这座桥分别需要耗时

[问答题]

有ABCD四个人要在夜里过一座桥，他们通过这座桥分别需要耗时1、2、5、10分钟，现在只有一支手电，过桥时必须带有手电，并且同时最多只能两个人一起过桥。请问如何安排能够让四个人尽快都过桥。

推荐

、V1V1

1和2 先过。1返回，5和10先过，2返回，1和2一起过。一共时间=2+1+10+2+2=17分钟

发表于 2014-11-02 16:33:52 回复(4)

刘大猫

这题关键应该是让耗时最接近的人一起走，最后让用时最短的人回来接和他耗时接近的那个人。所以我肯定要让10和5一起走。假如10和5第一个过去，难免用时最长的这俩其中的一个还要回去，浪费时间，所以在他俩去之前应该让一个耗时较短的人先过去。那就先让1和2过去，那现在有两种情况，1回来还是2回来呢?先假设1回来把手电给10和5，让他们过去，再让2回来接1，这种情况用时:2+1+10+2+2=17 那么假如让2回来把手电给10和5，等他们过去以后让1回来接2用时:2+2+10+1+2=17。结果一样。所以最关键的就是让1和2一起走，10和5一起走，至于1接2还是2接1，结果是一样的。

发表于 2017-08-22 14:37:27 回复(0)

C.C.

AB,A,CD,B,AB

发表于 2014-10-21 17:36:43 回复(0)

牛客951083号

AB先过桥，A拿着手电返回；CD再过桥，B拿着手电返回；最后AB一起过桥

发表于 2016-01-27 10:41:08 回复(0)

飞往彼岸

看了大家答案，这个用的是哪个算法？程序如何写？比如给定N个人。求最短时间。

发表于 2015-08-07 12:07:06 回复(1)

Jessica2015

A(1),B(2)过桥2两分钟，

2，

A(1)回去，1分钟

3，

C(5)，D(10)过桥，10分钟

4，

B（2）回来，2分钟

5，

A(1),B(2)过桥2两分钟

2+1+10+2+2=17分钟

发表于 2015-05-22 12:26:42 回复(0)

难顶啊

通解思路（个人愚见，思考不足之处请大家指正）：

1人:直接过去

2人:算两人中较大值

3人:出现需要人返回的情况，很明显让最快的人返回一次

4人（从快到慢为a,b,c,d四人）:按照3人时处理的方***想到每次都让a来回接人,但有时候在第二趟先让最慢的c和d一起回去，然后让b回来接人会更快。这就出现了两种情况ab,a,ac,a,ad(情况1，耗时b+a+c+a+d=2a+b+c+d)和ab,a,cd,b,ab(情况2，耗时b+a+d+b+b=a+3b+d),通过判断2b和a+c的大小，选择用情况1或者情况2处理。

。。。

n个人:忽略中间的人，只考虑前后各两个人，看做四人的情况，比较2b和a+c的大小，当出现较小的c使得2b>a+c时就按情况1处理，否则一直按情况2处理。

编辑于 2020-03-28 11:23:04 回复(0)

血江南

1.第一步：A(1分钟)和D(10分钟)过去，A（1分钟）带电筒回来，总共11分钟
2.第二步：A（1分钟）和C(5分钟)过去，A（1分钟）带电筒回来，总共6分钟
3.第三部：A(1分钟)和B（2分钟）过去，总共2分钟
全程最短时间：11+6+2=19分钟

发表于 2016-06-16 14:44:12 回复(0)

LUNU

D与ABC分别同时过桥

发表于 2021-09-06 15:21:27 回复(0)

TANG1

1.第一步：A(1分钟)和B(2分钟)过去，A（1分钟）带电筒回来，总共3分钟

2.第二步：C（5分钟）和C(10分钟)过去，B（2分钟）带电筒回来，总共12分钟

3.第三部：A(1分钟)和B（2分钟）过去，总共2分钟

全程最短时间：3+12+2=17分钟

发表于 2019-08-21 17:06:58 回复(0)

Corina_Shao

17分钟，但是这道题的通用数学解法是什么呢？

发表于 2018-04-18 10:29:12 回复(0)

国殇

10+5+2+1*2=19分钟，1陪他们慢慢走然后1返回再慢慢走，返回两次。

发表于 2016-10-11 10:25:42 回复(0)

牛客976311号

1,2 先一起过 2 分钟 === 4

510 后一起过 10 === 4 + 20

发表于 2016-10-08 14:09:16 回复(0)

daxiami101

假如现在只有三个人的话，过河时间分别为a1,a2,a3,且a1<=a2<=a3，则过河最短时间一定是a1+a2+a3（前提是，河对岸没有人的情况下），这只是作为一个参考模型。
现在多了一个人，好不疑问，必须要把4个人的情况，降低为3个人，且必须经历这样一个过程，因此在让第一个人过河时，必须使得时间最短。现在，把4个人的速度排序1，2，5，10。前两个前先过，时间当然是最短的，毫无疑问，2在对岸，1返回，共耗时3分钟。
好了，现在，问题回到了最初的模型，3人过河的问题，但唯一不同的是，河对岸现在是有人的，因此不能和之前的情况完全的相同。必须分情况。按什么分呢，显然是剩余三人的过河时间。
第一：现在我们忽略河对岸的人，完全按照最初的模型来进行计算，显然时间为1+5+10=16分钟；
第二：我们利用河对岸的人，并以此为资源，缩短过河时间。分析如下：时间最长的人，无论如何都要花费那么多的时间，因此让时间第二长的人和他一起过河，可以将第二人的时间完全的屏蔽掉，因此让5，10一起过河，共花费10分钟，此时1还在对岸，需要一人回去接应，当然此时应该让2去，因此，此过程花费4分钟。
把两种情况做简单的对比；第一种：3+16=19；第二种：3+10+4=17；
显然第二种要好。故共花费17分钟。
但是，有一点需要说明的是，并不是所有的情况都是第二种好。
比如1，3，4，5；

发表于 2016-01-20 22:16:08 回复(0)

狼族099

发表于 2015-09-12 09:58:52 回复(0)

幻影迷风

A带B过桥，再返回带C，再返回带D 总共耗时19分钟

发表于 2015-09-11 19:51:38 回复(0)

亦珍

<div> 1、首先 A和B,一起过桥， A 返回，两次共用时间 3分钟 </div> <div> 2、C 和D一起过桥，B返回，这两次共用时间为 12分钟 </div> <div> 3、A和B在一起过桥，用时 2分钟 </div> <div>  以上总共用时 3+12+2=17分钟 </div>

发表于 2015-09-11 16:51:18 回复(0)

遇见123

<div> 第一趟：A和B一起过桥，2分钟 </div> <div> 第二趟：A回来，1分钟 </div> <div> 第三趟：C和D过桥，10分钟 </div> <div> 第四趟：B回来，2分钟 </div> <div> 第五趟：A和B过桥，2分钟 </div> <div> 合计：2+1+10+2+2=17分钟 </div>

发表于 2015-09-07 12:44:11 回复(0)

s201302186

先让耗时最长的两个10分钟的和5分钟的先过，再让耗时最短的两个过。

发表于 2015-09-07 11:12:55 回复(1)

hfy

<div> 1.AB俩个先过桥，花费2分钟。 </div> <div> 2.A回来，花费1分钟。然后AC两个人过桥，花费5分钟。 </div> <div> 3.A回来，花费1分钟。然后AD两个人过桥，花费10分钟。 </div> <div> 总共花费19（2+1+5+1+10）分钟。 </div>

发表于 2015-09-07 09:03:10 回复(0)

丕子李

<pre class="prettyprint lang-java"> 要求浪费的时间最短即可，那么耗时1分钟的充当运输手电筒的作用 1. 1，10过桥需要10分钟，1返回，共耗时11分钟 2. 1，5过桥需要5分钟，1返回，共耗时6分钟 3. 1，2过桥需要2分钟所以一共需要11+6+2=19分钟</pre> <br />

发表于 2015-09-07 00:00:18 回复(0)

提交观点

问题信息

C++工程师美团 2013 Java工程师

来自：美团2013研发笔试卷

上传者：季末

难度：

38条回答 70收藏 32464浏览

有ABCD四个人要在夜里过一座桥，他们通过这座桥分别需要耗时

问题信息

热门推荐

相关试题