经典智力面试题:一家人过桥

共 1315字,需浏览 3分钟

 ·

2021-05-23 20:29


 来源 | 小K算法(ID:xiaok365

01
故事起源
小明一家人过桥,现在是黑夜,所以必须要有灯。小明过桥要1秒,弟弟要3秒,爸爸要6秒,妈妈要8秒,爷爷要12秒。
此桥每次最多可过2人,过桥速度依最慢者而定,灯在点燃后30秒就会熄灭。
请问小明一家应如何过桥?


02
思考
只有一盏灯,所以一个人过桥肯定不行,他还得把灯送回来。
那肯定得两个人一起过桥,同时还有一个人返回把灯送回来。
因为小明的耗时是最少的,那我们的第一想法就是由小明来拿灯并返回,分别和其它4人一起过桥。


03
小明拿灯
第一次,小明和弟弟一起过桥用3秒,返回1秒,还剩26秒。
第二次,小明和爸爸一起过桥用6秒,返回1秒,还剩19秒。
第三次,小明和妈妈一起过桥用8秒,返回1秒,还剩10秒。
第四次,因为爷爷要用12秒,时间不够,已经无法过桥了。那我们就要切换思路,还有没有更好的方法呢?


04
调整思维
先把每个人的耗时用图形展示出来,更直观。
可以把过桥想象成一个运输的过程,每次运输最大容量为2个矩形。

假设小明和爷爷组合,或者妈妈和爷爷组合如下:
因为一定是以最慢的为准,也就是以最长的矩形为准,可以发现小明和爷爷组合浪费了很多空间,而妈妈和爷爷组合就浪费的比较少。这就启示尽量让运输效率更高,也就是浪费的空间越少越好。


05
抽象描述
有5个长度不一的木块,现在要用箱子装下所有的木块,每个箱子最多装2个,箱子的宽度等于所装的最大木块的宽度,怎样装可以让所有箱子的宽度总和最小?
你品,你细品,如果不考虑返回送灯,是不是就很像上面的过桥问题。通过这种抽象描述,应该很多同学有一种熟悉的感觉。
是的,你没有猜错,是不是很像动态规划里面的多个背包啊。
不过这个问题还用不到动态规划,用贪心的思想即可,尽量让相等的放一起,就可以浪费更少的空间。


06
回到之前的问题
根据上面的思想,让耗时相等的尽量一起。
第一次,小明和弟弟一起过桥用3秒,小明返回1秒,还剩26秒。
第二次,妈妈和爷爷一起过桥用12秒,弟弟返回3秒,还剩11秒。
第三次,小明和爸爸一起过桥用6秒,小明返回1秒,还剩4秒。
第四次,小明和弟弟一起过桥用3秒,还有1秒。
小明一家人安全过桥,perfect。


07
总结
这类智力面试题,可以先尝试自己的第一感觉,如果不对就切换思路,思维不能局限,很快就可以发现规律了。

1、Intellij IDEA这样 配置注释模板,让你瞬间高出一个逼格!
2、吊炸天的 Docker 图形化工具 Portainer,必须推荐给你!
3、最牛逼的 Java 日志框架,性能无敌,横扫所有对手!
4、把Redis当作队列来用,真的合适吗?
5、惊呆了,Spring Boot居然这么耗内存!你知道吗?
6、全网最全 Java 日志框架适配方案!还有谁不会?
7、Spring中毒太深,离开Spring我居然连最基本的接口都不会写了

点分享

点收藏

点点赞

点在看

浏览 59
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报