POJ 2573 / ZOJ 1877 Bridge - 經典過橋問題的貪心策略與輸出路徑

經典的「過橋問題」：n 人需在夜晚通過一座只能容納兩人的橋，只有一盞燈，每人過橋速度不同，兩人同行按慢者速度。求所有人過橋的最短總時間，並輸出具體過橋方案。

核心貪心策略：兩種方案取優

設四人速度由快到慢為 a, b, c, d。將最慢的兩人 (c, d) 送過去有兩種方案：

1. 最快者穿梭：a 帶 d 過，a 回；a 帶 c 過，a 回。耗時：d + a + c + a = 2a + c + d。
2. 次快者協助：a, b 過，a 回；c, d 過，b 回。耗時：b + a + d + b = a + 2b + d。

每次處理最慢的兩人時，選擇耗時較小的方案。剩餘 3 人時：a + b + c；2 人：b；1 人：a。

輸出方案的實現細節

在計算最短時間的同時，記錄每一步的操作（誰過橋、誰回燈），最後按順序輸出。需注意輸出格式：每行兩人過橋或一人回燈。

代碼框架（關鍵邏輯）

sort(speed, speed + n);
int pos = n - 1;
while (pos >= 3) { // 處理最慢兩人
    int cost1 = 2*speed[0] + speed[pos] + speed[pos-1];
    int cost2 = 2*speed[1] + speed[0] + speed[pos];
    if (cost1 < cost2) {
        // 方案 1: a送d, a回, a送c, a回
        record(0, pos); record(0, -1);
        record(0, pos-1); record(0, -1);
    } else {
        // 方案 2: a,b過, a回, c,d過, b回
        record(0, 1); record(0, -1);
        record(pos-1, pos); record(1, -1);
    }
    pos -= 2;
}
// 處理剩餘 1~3 人
if (pos == 2) { record(0,1); record(0,-1); record(0,2); }
else if (pos == 1) { record(0,1); }
else if (pos == 0) { record(0,-1); }

總結

過橋問題的關鍵在於證明「每次處理最慢的兩人」的貪心選擇性質，並正確比較兩種核心方案。輸出路徑只需在決策時同步記錄操作序列即可。