蚂蚁爬杆 - 编程之美 4.7

http://www.cnblogs.com/Linkabox/p/3359828.html
问题：有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过两只蚂蚁。开始时，蚂蚁头朝向任意（左或右），它们只会朝前或掉头，不会后退。当任意两只蚂蚁碰头是，两只蚂蚁会同时调头朝反向走。假设蚂蚁每秒走1厘米，编写程序，求所有蚂蚁都离开木杆的最短时间和最长时间。

解法二：

细心分析一下蚂蚁的运动及其行走的路径，可以得出一些有用的信息，例如两只蚂蚁A、B运动如下图所示：

A与B相遇，然后反向前进，最后A与B都离开了木杆，A总共走了6，B总共走了4。

若A与B相遇时，不是反向前进而是擦肩而过，继续前进，A走了5，B也走了5。

可以看出将“掉头走”看作“擦肩而过”，这样蚂蚁的运动就是独立的，其实A代替了B走，B代替了A走。

这样所有的蚂蚁运动轨迹可能与原来不同，但不影响所有蚂蚁离开木杆的最短时间和最长时间。

void CalcTime(double PoleLen,double *xPos,int AntNum,double speed,double &tMin,double &tMax)
{
    tMax=tMin=0;
    for(int i=0;i<AntNum;++i)
    {
        double curMax=0;
        double curMin=0;
        if (xPos[i]>(PoleLen/2))
        {
            curMax=xPos[i];
        }
        else
        {
            curMax=(PoleLen-xPos[i]);
        }
        curMin = PoleLen - curMax;
        if (tMax < curMax)
        {
            tMax = curMax;
        }
        if (tMin < curMin)  //注意这里是小于因为是所有蚂蚁最短时间，取最短中最大的
        {
            tMin = curMin;
        }
    }
    tMax/=speed;
    tMin/=speed;
}

http://lam8da.sinaapp.com/?p=11
从左边数起的第i只蚂蚁什么时候走出木杆？

我们假设每只蚂蚁都背着一袋粮食，任意两只蚂蚁碰头时交换各自的粮食然后调头。这种情况下，每次有一只蚂蚁离开木杆都意味着一袋粮食离开木杆（虽然可能已经不是它刚开始时背的那一袋了）。于是，我们可以求出每袋粮食离开木杆的时间（因为粮食是不会调头的）。又由于每袋粮食离开木杆的时间都对应某只蚂蚁离开木杆的时间，这是一种一一映射关系。现在我们要找到对应于第i只蚂蚁的那个映射。在此之前需要证明一个命题：

若一开始时有M只蚂蚁向左走，N−M只蚂蚁向右走，则最终会有M只蚂蚁从木杆左边落下，N−M只蚂蚁从木杆右边落下。

这个命题很容易证明：每次碰撞均不改变向左和向右的蚂蚁数量。于是，由于每次碰撞蚂蚁都会调头而不是穿过，最后必定是从左边数起的前M只蚂蚁从左边落下，后N−M只蚂蚁从木杆右边落下。由于我们知道每袋粮食是从哪边落下的，故左边落下的M袋粮食的离开木杆的时间就对应于从左边数起的前M只蚂蚁离开木杆的时间，右边的类似。因此，我们只需判断i和M的关系，便知道第i只蚂蚁是从左边还是右边落下。不妨假设是从左边落下，因此该蚂蚁落下的时间就等于从左边落下的第i袋粮食的落下时间。时间复杂度O(N)，一遍扫描搞定。

所有蚂蚁从一开始到全部离开木杆共碰撞了多少次？
对于扩展2，我们只需求得每个蚂蚁的碰撞次数，然后累加即可。在这里我们换一种思路，把碰撞调头看成不调头而继续向前（穿过），则容易看出原问题（碰撞次数）就变为求穿过的次数（因为速度大小不变，原来的每次碰撞都对应于现在的一次穿过）。则对于每只向左的蚂蚁，它只会“穿过”那些在它左边的向右走的蚂蚁。因此，每只蚂蚁“穿过”的蚂蚁次数等于刚开始时在它前进方向上与它前进方向相反的蚂蚁个数。时间复杂度也是O(N)。
第k次碰撞发生在哪个时刻？哪个位置？哪两个蚂蚁之间？

第3个扩展问题有点复杂。首先我们假设v为0.5个单位长度每秒，每个蚂蚁刚开始时都处于整点处，这样每次碰撞都发生在整秒处。这个假设有个好处，就是我们可以二分第k次碰撞的时刻。如果碰撞时刻是浮点数，这个二分有可能永远不会终止。我们还是看成每个蚂蚁驮着一袋粮食，那么每袋粮食易主（即从一个蚂蚁身上交换到另一个蚂蚁身上）时，就发生了一次碰撞。由于粮食的方向是固定不变的，我们可以很容易求出每一袋粮食在它的“前进”方向上的所有易主时刻（它易主的次数等于扩展2中的“穿过”次数）。这样，我们的问题就等价于：

找到最小的时间t，使得易主时刻小于或等于t的易主次数大于或等于k。

由于现在所有碰撞（易主）的时刻都是整点，故我们可以二分t，然后用线性复杂度找出易主时刻小于或等于t的易主次数。整个复杂度为O(N∗log(|maxt−mint|)，其中maxt和mint分别表示第一次和最后一次碰撞的时刻，均可在O(N)时间内求出。

在上一段中，要想使用线性时间复杂度求出易主时刻小于或等于t的易主次数还需要一点技巧。可以这样：用一个数组pi表示第i个向右走的蚂蚁的初始位置，当扫描到第j个向左走的蚂蚁时，假设得到的中值点为i′（即p0到第pi′个位置上对应的粮食和该袋粮食的易主时刻均大于t）。由于该袋粮食向左易主的时刻是递增的，而下一个向左走的蚂蚁的初始位置又大于当前（第j个向左走的）蚂蚁，故对于下一个蚂蚁ant来说，p0到第pi′个位置上对应的粮食和ant所驮粮食的易主时刻也一定大于t。即中值点的位置是单调的。因此可以在均摊O(N)的时间内算出所求个数。

求出时刻的同时我们也求出了位置，故第二小问也解决。接下来要求哪两个蚂蚁发生了这次碰撞（如果同时存在多个碰撞求出任意一个即可）。其实，我们只需要求出每袋粮食在t时刻的位置即可。因为每袋粮食必然对应于一个驮着它的蚂蚁，故我们只需对这些粮食的位置排序，找出位置相同的粮食以及其下标（即从左到右第几个），也就找出了那对蚂蚁了。

哪只蚂蚁的碰撞次数最多？对于第4个扩展，只要求出每只蚂蚁的碰撞次数即可。这也解决了扩展2的解答中原始思路。首先由扩展1的解答我们可以知道每只蚂蚁最终是往左还是右掉下去，然后假设第i只蚂蚁最终往左掉下，而开始时刻其左边有r只向右走的蚂蚁，则它至少要朝左边碰撞r次才能把左边的蚂蚁全撞成向左的状态。倘若它一开始就是向左的，则共要碰撞2r次，否则为2r+1次。这样利用一个数组和几个计数器仍能在O(N)时间内求出每个蚂蚁的碰撞次数，取最大那个即可。
如果不是一根木杆而是一个铁圈，经过一段时间后所有蚂蚁都会回到的状态吗？这个时间的上界是多少？

这个问题看起来挺复杂，其实很简单。假设环长为L，则一个蚂蚁走完一圈需要T=L/v的时间。首先，还是像上面的讨论那样假设每个蚂蚁都驮着一袋粮食。那么，经过T时间后所有粮食都回到了原来的位置。由于每袋粮食都对应一个蚂蚁，而蚂蚁每次碰撞都会调头，因此蚂蚁的相对位置是不变的，这就说明经过T时间后蚂蚁循环移动了。假设移动了s个位置，即每个蚂蚁都到达它往右第s个蚂蚁的初始位置，那么，类似地，再经过T时间，当前状态仍会循环移动s个位置。容易看出这是一个最小公倍数问题：循环移动多少个s次之后每个蚂蚁回到自己位置？答案为LCM(N,s)/s，于是最多经过Tmax=LCM(N,s)/s∗T≤N∗T时间，每个蚂蚁都至少回到原地一次。

除了以上几个扩展，还有一些个人认为比较变态的扩展，有的没空仔细想，有的暂时没想到解法，也列出如下，欢迎拍砖：

1. 如果每只蚂蚁的速度不一样（这就有可能由于追赶而产生碰撞，此时根据动量守恒定律:(，速度互换），上述扩展问题的答案是什么呢？
2. 如果蚂蚁在一个平面上运动，同样也是碰头后原路返回（注意这不等同于两只蚂蚁交换继续前进），问是否所有蚂蚁都能最终离开平面？
3. 在上述情况下，如果最终能离开平面，离开平面需要多长时间？
4. 在上述情况下，回答关于一维的前文讨论的每个问题。

另外，赵牛同学又提出了一些更bt的扩展，如下：

1. 假设每个蚂蚁都有重量，两只蚂蚁碰撞时轻的那个有一定几率从旁边被撞下去:(，那又该怎样？
2. 假设不是被撞下去而是有一定几率被撞晕而停滞几秒，那又该怎样？

http://blog.csdn.net/weichaohnu/article/details/8748138

4、鸽子共飞了多少路程？

这个比较简单，不要想鸽子飞来飞去，直接以时间为基准来考虑就行了。c*(s/(a+b))

5、什么时候轮船可找到救生圈

简单的，1个小时

BTW在看这个扩展题[2]的时候，看到博主贴的一个某度的面试题，的确挺有一次，原题+解题思路都摘过来了

皆转自[2]

原题如下：

    山上有五个山洞排成一行，编号从1到5。有个狐狸，它第一天藏在某个山洞中，从第二天开始，每天可以逃到前一天所在山洞相邻的山洞中，但逃到哪一个是随机的（当然如果狐狸当前在1号山洞那么它第二天只能去2号洞了，5号也类似）。有个猎人，他每天只能搜寻一个山洞（因为山洞太复杂了。。。。），如果狐狸当天在他搜寻的山洞中就被逮到了。问猎人是否有必定能抓住狐狸的策略？

解题思路：思路的确是非常巧妙，其实就是一个奇偶性的判断。只要猎人知道狐狸是在偶数号洞还是奇数号洞就可以了。比方说，猎人知道狐狸是在偶数号洞里，那猎人只要第一天待2号洞，第二天待3号洞，第三天待4号洞，最晚第三天必然能抓到狐狸，因为猎人和狐狸都在偶数号洞里，那么猎人和狐狸的距离差偶数大小，而猎人每经过一天，和狐狸的距离要么不变，要么减2，所以总会相互！

狐狸在奇数号洞里同样如此，猎人选择从奇数号洞开始待就可以了。

所以关键是猎人如何确定狐狸到底是在奇数号洞还是在偶数号洞里！

方法差不多，猎人从1号洞开始待，一直到第四天待到4号洞，都没抓住狐狸，说明狐狸第四天待在奇数号洞里，那第五天狐狸必然要去偶数号洞里拉...(自己想想为什么)

还想不明白的读者就去参看[2]吧...

附上对于n个洞的答案：

不论n多大，最坏情况下只需2n−4天就能逮到狐狸，策略是这样的：

若n为奇数，则从第一天开始搜寻的山洞编号为：2, 3, 4, …, n-1, 2, 3, 4, …, n-1

若n为偶数，则从第一天开始搜寻的山洞编号为：2, 3, 4, …, n-1, n-1, n-2, …, 3, 2

不管哪种情况，只需2n−4步即可逮到狐狸。