螞蟻在木桿上：經典算法問題的巧妙解法

問題描述

有一根長 27 公分的細木桿，在 3、7、11、17、23 公分處各有一隻螞蟻。木桿極窄，螞蟻無法互相通過。開始時，每隻螞蟻朝左或朝右的方向任意，牠們只會向前走或調頭，不會後退。當兩隻螞蟻相遇（碰頭）時，兩隻會同時調頭朝反方向走。假設螞蟻每秒走 1 公分。求所有螞蟻離開木桿的最小時間與最大時間。

核心洞見：碰撞等價於穿越

這道題的關鍵在於一個反直覺的觀察：當兩隻螞蟻碰頭並調頭時，等價於兩隻螞蟻互不干擾地穿越彼此繼續前進。

想像螞蟻 A 在 3 公分處向右走，螞蟻 B 在 7 公分處向左走。牠們在 5 公分處相遇並調頭。A 最終會走到左端（0 公分），走過 3 公分；B 最終會走到右端（27 公分），走過 20 公分。總路程 = 3 + 20 = 23 公分。

若視為兩隻螞蟻穿越彼此：原本在 3 公分的螞蟻繼續向右走到 27 公分（24 公分），原本在 7 公分的螞蟻繼續向左走到 0 公分（7 公分）。總路程同樣是 24 + 7 = 31 公分？等等——其實螞蟻的身份交換了。若不關心「哪隻螞蟻是哪隻」，只關心「什麼時候所有螞蟻都離開」，碰撞調頭與穿越的效果完全一致：每個位置上都會有一隻螞蟻以相同速度離開。因此，計算時間時可以完全忽略碰撞調頭規則，視為螞蟻互不干擾地直線行走。

最小時間與最大時間的計算

• 最小時間：每隻螞蟻都選擇走向離自己最近的那一端。對位置 x，最近端距離為 min(x, L - x)。所有螞蟻中耗時最久的那隻決定了最小時間，即 max(min(x_i, L - x_i))。本題中，位置 11 公分的螞蟻到最近端（左端）需 11 秒，為最大值，故最小時間 = 11 秒。
• 最大時間：每隻螞蟻都選擇走向離自己最遠的那一端。對位置 x，最遠端距離為 max(x, L - x)。所有螞蟻中耗時最久的那隻決定了最大時間，即 max(max(x_i, L - x_i))。本題中，位置 3 公分的螞蟻到最遠端（右端）需 24 秒，位置 23 公分的螞蟻到最遠端（左端）需 23 秒，最大值為 24 秒，故最大時間 = 24 秒。

通用 C 語言實現

以下程式接受命令列參數：木桿長度 L、螞蟻數量 n、螞蟻位置列表（逗號分隔），輸出最小與最大時間。

#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a > b ? b : a; }

int main(int argc, char** argv) {
    if (argc != 4) {
        printf("Usage: %s L n positions\nExample: %s 27 5 3,7,11,17,23\n", argv[0], argv[0]);
        return 1;
    }
    int L = atoi(argv[1]);
    int n = atoi(argv[2]);
    char *token = strtok(argv[3], ",");
    int minTime = 0, maxTime = 0;
    while (token) {
        int pos = atoi(token);
        minTime = max(minTime, min(pos, L - pos));
        maxTime = max(maxTime, max(pos, L - pos));
        token = strtok(NULL, ",");
    }
    printf("min time: %ds, max time: %ds\n", minTime, maxTime);
    return 0;
}

編譯與執行範例

gcc ant.c -o ant
./ant 27 5 3,7,11,17,23
# 輸出: min time: 11s, max time: 24s

延伸思考

這個問題展示了「等價轉換」在算法設計中的威力：將看似複雜的交互行為（碰撞調頭）轉化為簡單的獨立行為（直線行走），從而輕鬆求解。同樣的思想常見於粒子碰撞、交通流模型等領域。