POJ 1700 Crossing River 詳解：過河問題貪心策略

題目大意

N 人需過河，僅有一條船，每次最多載 2 人。每人划船速度不同，兩人同行按較慢者計時。求所有人過河的最短總時間。N ≤ 1000，時間 ≤ 100 秒，T ≤ 20 測試用例。

核心策略：兩種送最慢者過河方案

設速度排序後為 a[0] ≤ a[1] ≤ ... ≤ a[n-1]。最慢的兩人 a[n-2], a[n-1] 過河有兩種方案：

方案 1：兩最快者作摆渡

1. a[0], a[1] 過河 → 時間 a[1]
2. a[0] 回 → 時間 a[0]
3. a[n-2], a[n-1] 過河 → 時間 a[n-1]
4. a[1] 回 → 時間 a[1]
5. 小計：2*a[1] + a[0] + a[n-1]

方案 2：最快者陪同最慢者

1. a[0], a[n-1] 過河 → 時間 a[n-1]
2. a[0] 回 → 時間 a[0]
3. a[0], a[n-2] 過河 → 時間 a[n-2]
4. a[0] 回 → 時間 a[0]
5. 小計：2*a[0] + a[n-2] + a[n-1]

選擇策略

比較 2*a[1] vs a[0] + a[n-2]：

• 若 2*a[1] < a[0] + a[n-2] → 選方案 1
• 否則 → 選方案 2

重複處理剩餘最慢的兩人，直到剩 ≤ 3 人。

基本情況處理

完整代碼

#include 
using namespace std;

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        vector a(n);
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        sort(a.begin(), a.end());
        
        int total = 0;
        int i = n - 1;
        while (i >= 3) {
            // 兩種方案取較小
            int cost1 = 2*a[1] + a[0] + a[i];
            int cost2 = 2*a[0] + a[i-1] + a[i];
            total += min(cost1, cost2);
            i -= 2;  // 處理掉兩個最慢的
        }
        // 基本情況
        if (i == 2) total += a[0] + a[1] + a[2];
        else if (i == 1) total += a[1];
        else if (i == 0) total += a[0];
        
        printf("%d\n", total);
    }
    return 0;
}

範例驗證

輸入：4 人，速度 1 2 5 10

• 排序：[1,2,5,10]
• i=3：cost1=2*2+1+10=15, cost2=2*1+5+10=17 → 選 15
• 剩 i=1：total += 2
• 結果：17 ✓

複雜度分析

• 排序：O(N log N)
• 貪心循環：O(N)
• 總體：O(N log N) 時間，O(N) 空間

關鍵點總結

1. 貪心選擇證明：最慢者必須過河，僅有兩種基本模式，每步取局部最優得全局最優
2. 排序是前提：必須先按速度升序排列
3. 邊界情況：N=1,2,3 需單獨處理
4. 數據範圍：總時間 ≤ 1000×100 = 10⁵，int 足夠

總結

POJ 1700 是經典貪心問題。核心在於識別「送最慢兩人過河」的兩種基本模式，並通過比較 2*a[1] 與 a[0]+a[n-2] 決策。此類「接送問題」常見於算法競賽，掌握模式匹配與貪心證明思路至關重要。