2013年08月15日

蚂蚁蚂蚁


这道题是陈利人老师在待字闺中发布的,题为蚂蚁蚂蚁,具体题目如下。

n只蚂蚁以每秒1cm的速度在长度为Lcm的竿子上爬行。蚂蚁爬到终点会掉下来,两只蚂蚁相遇时,只能调头爬回去。对于每一只蚂蚁i,给定其距离竿子左端的距离X[i],但是我们不知道蚂蚁的初始朝向。计算,所有蚂蚁掉落需要的最短时间和最长时间。

分析

这道题看上去很复杂,但是存在一个小技巧,就是所有的蚂蚁都以同样的速度前行,也就是说,如果两只蚂蚁A和B,从各自的位置出发,加入A朝右走,而B朝左走。这样两只蚂蚁会相遇,相遇之后,则,A朝左走,B朝右走。问题就在此了,因为两只蚂蚁的移动速度是一样的,因此可以把朝左的蚂蚁A当成是蚂蚁B,朝右走的蚂蚁B看成是蚂蚁A,这样,就无所谓相撞的问题了。

最短的时间就是所有的蚂蚁都朝自己近的方向走,所有蚂蚁中离自己最近方向的最大距离便是最短的时间。

最长的时间就是查找所有蚂蚁中距离某端最远的距离。

总结

这个题目虽说简单,但是蛮有启发性,初次看上去感觉所有蚂蚁的方向不明确,会相撞N多次,处于很混乱的情况,而实际上蚂蚁都是一样的,一样的速度前进,则可以换个思维理解,问题并破了。

前一篇: 旋转图片 后一篇: Python Metaclass学习