原题
n只蚂蚁以每秒1cm的速度在长为Lcm的竿子上爬行。蚂蚁爬到终点会掉下来。两只蚂蚁相遇时，只能调头爬回去。对于每一只蚂蚁i，给定其距离竿子左端的距离x[i]，但是我们不知道蚂蚁的初始朝向。计算，所有蚂蚁掉落需要的最短时间和最长时间。
分析
根据题目描述，我们不知道蚂蚁的初始朝向，所以两种都有可能。此时，我们可以先固定第0个蚂蚁的方向，然后再处理其他的蚂蚁。这是一个递归的思路，并且每个蚂蚁有两个选择，一共2^n种情况，计算每一种情况下，所有蚂蚁掉落的时间，选择最短的、最大的则得到答案。这个题目的时间复杂度是指数级的。真真有些高了，那么如何改进呢？
我们在摘要中说道，这个题目其实是考察大家想象力的。想象力在哪里呢？我们首先来看看最短时间的情况，直觉上来讲，所有的蚂蚁都超最近的一端走，是需要最短时间的。那么这时，会不会发生碰撞呢？显然是不能的，A和B是两只不同的蚂蚁。
| … | B | A | … |
假设A到左端近，距离为LA
下面考虑最长时间的情况，也是该发挥想象力的地方。当两只蚂蚁相遇的时候，本来是要调头爬回去的。这与直接交错走过去有什么不同呢？蚂蚁的速度是一样的。大家可以举几个具体的例子，看看这两种情况，差别在哪里。例如:
| B | A |
*当相遇调头时，A和B都调下来的最长时间是4秒。A向左一格，然后调头向右三格*当相遇交错走过时，A向左走三格掉落，B向右走四格掉落。则最长时间为4秒。这并不是巧合。可以认为是同样的情况。主要的原因就是蚂蚁的速度是相同的，可以认为是独立的。这样，求所有蚂蚁都掉落的最长时间，就是找离某一端距离最长的蚂蚁，然后向着这一端走，所需要的时间。算法的时间复杂度为O(n)。
后面求最长时间的关键就是，发挥想象，找到调头和交错走过实际上是一样的。就搞定了。
【分析完毕】
本文来自微信：待字闺中，2013-08-13发布，原创@陈利人 ，欢迎大家继续关注微信公众账号“待字闺中”。