螞蟻掉落木棒問題：經典算法題解與數學建模分析

螞蟻掉落木棒問題：經典算法題解與數學建模分析

問題描述

一根長度為 L 厘米的木棒上有 N 隻螞蟻，每隻螞蟻以 1 厘米/秒的速度向左或向右行走。當兩隻螞蟻相撞時，它們同時掉頭（掉頭時間忽略不計）。已知每隻螞蟻距離木棒左端的距離，求多少秒後所有螞蟻剛好都從木棒上掉下來。
約束條件：N, L ≤ 1000。

輸入格式

• 第一行：兩個整數 N 和 L
• 接下來 N 行：每行一個字符（L 或 R）表示方向，和一個整數 x 表示距離左端距離

樣例

輸入：
4 10
R 1
R 5
L 3
R 9

輸出：
9

核心洞察：碰撞等價於穿透

關鍵觀察：兩隻螞蟻相撞後掉頭，與它們直接穿過彼此繼續前進，對「最後一隻螞蟻掉落的時間」完全等價。

原因：螞蟻不可區分，碰撞交換身份後繼續移動，等同於兩隻螞蟻保持原方向穿過對方。因此，每隻螞蟻的掉落時間僅取決於其初始位置和朝向，與碰撞無關。

數學模型

• 向左走（L）的螞蟻：掉落時間 = 距離左端距離 x
• 向右走（R）的螞蟻：掉落時間 = L - x
• 答案 = 所有螞蟻掉落時間的最大值

算法實現

#include <stdio.h>

int main() {
    int N, L;
    scanf("%d %d", &N, &L);
    
    int maxTime = 0;
    for (int i = 0; i < N; i++) {
        char dir;
        int x;
        scanf(" %c %d", &dir, &x); // 注意 %c 前的空格跳過換行符
        
        int time = (dir == 'R') ? (L - x) : x;
        if (time > maxTime) maxTime = time;
    }
    
    printf("%d\n", maxTime);
    return 0;
}

複雜度分析

• 時間複雜度：O(N)，單次遍歷
• 空間複雜度：O(1)，僅需常數額外空間

題後反思

1. 動手模擬：拿筆紙畫幾個簡單案例（如 2 隻螞蟻對撞），觀察軌跡，直觀驗證「穿透等價性」。
2. 抓住本質：題目問「所有螞蟻掉落的時間」即「最後一隻掉落時間」，轉化為求最大值問題。
3. 不要被細節干擾：碰撞、掉頭看似復雜，實則是干擾項，核心是獨立運動。

擴展思考

若螞蟻有大小、速度不同、或木棒有彈性邊界，問題將如何變化？這些變體考察的是建模能力與邊界條件處理。