http://lam8da.sinaapp.com/?p=11

《編程之美》4.7節(jié)描述了螞蟻爬桿問題，把所有具體數(shù)字都表示成字母后變?yōu)樾稳缛缦滦问降膯栴}：

有一根長為L的平行于x軸的細木桿，其左端點的x坐標為0（故右端點的x坐標為L）。剛開始時，上面有N只螞蟻，第i(1≤i≤N)只螞蟻的橫坐標為xi（假設(shè)xi已經(jīng)按照遞增順序排列），方向為di（0表示向左，1表示向右），每個螞蟻都以速度v向前走，當任意兩只螞蟻碰頭時，它們會同時調(diào)頭朝相反方向走，速度不變。編寫程序求所有螞蟻都離開木桿需要多長時間。

該問題是經(jīng)典問題了，有O(N)的解法。昨天和趙牛同學討論了該問題的一些擴展，趙牛均給出了精妙解答，現(xiàn)列出如下：

第i只螞蟻什么時候走出木桿？

所有螞蟻從一開始到全部離開木桿共碰撞了多少次？

第k次碰撞發(fā)生在哪個時刻？哪個位置？哪兩個螞蟻之間？

哪只螞蟻的碰撞次數(shù)最多？

如果不是一根木桿而是一個鐵圈，經(jīng)過一段時間后所有螞蟻都會回到的狀態(tài)嗎？這個時間的上界是多少？

擴展1的解答

現(xiàn)在來解決擴展1。這個解答甚是精妙，通俗點來說，我們假設(shè)每只螞蟻都背著一袋糧食，任意兩只螞蟻碰頭時交換各自的糧食然后調(diào)頭。這種情況下，每次有一只螞蟻離開木桿都意味著一袋糧食離開木桿（雖然可能已經(jīng)不是它剛開始時背的那一袋了）。于是，我們可以求出每袋糧食離開木桿的時間（因為糧食是不會調(diào)頭的）。又由于每袋糧食離開木桿的時間都對應某只螞蟻離開木桿的時間，這是一種一一映射關(guān)系。現(xiàn)在我們要找到對應于第i只螞蟻的那個映射。在此之前需要證明一個命題：

若一開始時有M只螞蟻向左走，N?M只螞蟻向右走，則最終會有M只螞蟻從木桿左邊落下，N?M只螞蟻從木桿右邊落下。

這個命題很容易證明：每次碰撞均不改變向左和向右的螞蟻數(shù)量。于是，由于每次碰撞螞蟻都會調(diào)頭而不是穿過，最后必定是前M只螞蟻從左邊落下，后N?M只螞蟻從木桿右邊落下。由于我們知道每袋糧食是從哪邊落下的，故左邊落下的M袋糧食的離開木桿的時間就對應于前M只螞蟻離開木桿的時間，右邊的類似。因此，我們只需判斷i和M的關(guān)系，便知道第i只螞蟻是從左邊還是右邊落下。不妨假設(shè)是從左邊落下，因此該螞蟻落下的時間就等于從左邊落下的第i袋糧食的落下時間。時間復雜度O(N)，一遍掃描搞定。

擴展2的解答

對于擴展2，我們只需求得每個螞蟻的碰撞次數(shù)，然后累加即可。在這里我們換一種思路，把碰撞調(diào)頭看成不調(diào)頭而繼續(xù)向前（穿過），則容易看出原問題（碰撞次數(shù)）就變?yōu)榍蟠┻^的次數(shù)（因為速度大小不變，原來的每次碰撞都對應于現(xiàn)在的一次穿過）。則對于每只向左的螞蟻，它只會“穿過”那些在它左邊的向右走的螞蟻。因此，每只螞蟻“穿過”的螞蟻次數(shù)等于剛開始時在它前進方向上與它前進方向相反的螞蟻個數(shù)。時間復雜度也是O(N)。改為用糧食的觀點來理解也是可以的。

擴展3的解答

第3個擴展問題有點復雜。首先我們假設(shè)v為0.5個單位長度每秒，每個螞蟻剛開始時都處于整點處，這樣每次碰撞都發(fā)生在整秒處。這個假設(shè)有個好處，就是我們可以二分第k次碰撞的時刻。如果碰撞時刻是浮點數(shù)，這個二分有可能永遠不會終止。我們還是看成每個螞蟻馱著一袋糧食，那么每袋糧食易主（即從一個螞蟻身上交換到另一個螞蟻身上）時，就發(fā)生了一次碰撞。由于糧食的方向是固定不變的，我們可以很容易求出每一袋糧食在它的“前進”方向上的所有易主時刻（它易主的次數(shù)等于擴展2中的“穿過”次數(shù)）。這樣，我們的問題就等價于：

找到最小的時間t，使得易主時刻小于或等于t的易主次數(shù)大于或等于k。

由于現(xiàn)在所有碰撞（易主）的時刻都是整點，故我們可以二分t，然后用線性復雜度找出易主時刻小于或等于t的易主次數(shù)。整個復雜度為O(N?log(|maxt?mint|)，其中maxt和mint分別表示第一次和最后一次碰撞的時刻，均可在O(N)時間內(nèi)求出。

在上一段中，要想使用線性時間復雜度求出易主時刻小于或等于t的易主次數(shù)還需要一點技巧。可以這樣：用一個數(shù)組pi表示第i個向右走的螞蟻的初始位置，當掃描到第j個向左走的螞蟻時，假設(shè)得到的中值點為i′（即p0到第pi′個位置上對應的糧食和該袋糧食的易主時刻均大于t）。由于該袋糧食向左易主的時刻是遞增的，而下一個向左走的螞蟻的初始位置又大于當前（第j個向左走的）螞蟻，故對于下一個螞蟻ant來說，p0到第pi′個位置上對應的糧食和ant所馱糧食的易主時刻也一定大于t。即中值點的位置是單調(diào)的。因此可以在均攤O(N)的時間內(nèi)算出所求個數(shù)。

求出時刻的同時我們也求出了位置，故第二小問也解決。接下來要求哪兩個螞蟻發(fā)生了這次碰撞（如果同時存在多個碰撞求出任意一個即可）。其實，我們只需要求出每袋糧食在t時刻的位置即可。因為每袋糧食必然對應于一個馱著它的螞蟻，故我們只需對這些糧食的位置排序，找出位置相同的糧食以及其下標（即從左到右第幾個），也就找出了那對螞蟻了。

擴展4的解答

對于第4個擴展，只要求出每只螞蟻的碰撞次數(shù)即可。這也解決了擴展2的解答中原始思路。首先由擴展1的解答我們可以知道每只螞蟻最終是往左還是右掉下去，然后假設(shè)第i只螞蟻最終往左掉下，而開始時刻其左邊有r只向右走的螞蟻，則它至少要朝左邊碰撞r次才能把左邊的螞蟻全撞成向左的狀態(tài)。倘若它一開始就是向左的，則共要碰撞2r次，否則為2r+1次。這樣利用一個數(shù)組和幾個計數(shù)器仍能在O(N)時間內(nèi)求出每個螞蟻的碰撞次數(shù)，取最大那個即可。

擴展5的解答

這個問題看起來挺復雜，其實很簡單。假設(shè)環(huán)長為L，則一個螞蟻走完一圈需要T=L/v的時間。首先，還是像上面的討論那樣假設(shè)每個螞蟻都馱著一袋糧食。那么，經(jīng)過T時間后所有糧食都回到了原來的位置。由于每袋糧食都對應一個螞蟻，而螞蟻每次碰撞都會調(diào)頭，因此螞蟻的相對位置是不變的，這就說明經(jīng)過T時間后螞蟻循環(huán)移動了。假設(shè)移動了s個位置，即每個螞蟻都到達它往右第s個螞蟻的初始位置，那么，類似地，再經(jīng)過T時間，當前狀態(tài)仍會循環(huán)移動s個位置。容易看出這是一個最小公倍數(shù)問題：循環(huán)移動多少個s次之后每個螞蟻回到自己位置？答案為LCM(N,s)/s，于是最多經(jīng)過Tmax=LCM(N,s)/s?T≤N?T時間，每個螞蟻都至少回到原地一次。

除了以上幾個擴展，還有一些個人認為比較變態(tài)的擴展，有的沒空仔細想，有的暫時沒想到解法，也列出如下，歡迎拍磚：

如果每只螞蟻的速度不一樣（這就有可能由于追趕而產(chǎn)生碰撞，此時根據(jù)動量守恒定律:(，速度互換），上述擴展問題的答案是什么呢？

如果螞蟻在一個平面上運動，同樣也是碰頭后原路返回（注意這不等同于兩只螞蟻交換繼續(xù)前進），問是否所有螞蟻都能最終離開平面？

在上述情況下，如果最終能離開平面，離開平面需要多長時間？

在上述情況下，回答關(guān)于一維的前文討論的每個問題。

另外，趙牛同學又提出了一些更bt的擴展，如下：

假設(shè)每個螞蟻都有重量，兩只螞蟻碰撞時輕的那個有一定幾率從旁邊被撞下去:(，那又該怎樣？

假設(shè)不是被撞下去而是有一定幾率被撞暈而停滯幾秒，那又該怎樣？

blablabla...

總結(jié)

以上是生活随笔為你收集整理的蚂蚁爬杆的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。