#每日一面BAT#第22题 木杆蚂蚁


有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
木杆很细,不能同时通过一只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。
当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。
编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。
已邀请:

YangL - 成为一个优秀的人

赞同来自: pingpo


如下图,考虑任意两只蚂蚁的情况:
test.jpg

则:
①如果两只蚂蚁是相向运动,如图 假定A向右 B向左 它们会在m处相遇。接着同时掉头向相反的方向移动,最终离开木杆。
在上述过程中,A B两只蚂蚁总共的路程分别为:
SA = Am+ms SB=Bm+me
路程之和S = SA + SB =AB + SE = Ae + Bs 显然这是个常数
也就是说相向运动时 对蚂蚁离开木杆的时间没有影响。同时S = Ae + Bs也表明:
相向运动的蚂蚁相遇后掉头 等价于 两只蚂蚁相遇后不掉头仍然按照原先的运动方向至相应的终点。(对A来说是 e,对B来说是s)

因此,对时间有影响的运动是同向运动的蚂蚁。
②考虑同向运动的蚂蚁
最小时间离开木杆 <=> 每只蚂蚁朝离它最近的端点走。
最大时间离开木杆 <=> 每只蚂蚁朝离它最远的端点走。

对于多只蚂蚁的情况,按照②中的方法,比较所有蚂蚁的路程和,求对应情况下路程最大的蚂蚁所花时间即可。

要回复问题请先登录注册