POJ 1700 Crossing River 貪心策略最小化過河總時間

題目重述

N 人需過河，唯一小船每次最多載 2 人，划槳速度以較慢者為準。求所有人過河的最短總時間。

貪心核心：兩種送最慢者過河的方案

排序後設 a[0] ≤ a[1] ≤ … ≤ a[n-1]。每次處理最慢的兩人 a[n-1], a[n-2]，有兩種可行策略：

1. 方案一（最快者充當摆渡）：
   a[0] + 2*a[1] + a[n-1]
   過程：a[0],a[1] 過河 → a[0] 回 → a[n-2],a[n-1] 過河 → a[1] 回。
2. 方案二（最快者單獨陪同）：
   2*a[0] + a[n-2] + a[n-1]
   過程：a[0],a[n-1] 過河 → a[0] 回 → a[0],a[n-2] 過河 → a[0] 回。

每輪取兩者較小值，將問題規模減 2，直到剩 ≤ 3 人直接處理。

邊界情況

• n == 1：a[0]
• n == 2：a[1]
• n == 3：a[0] + a[1] + a[2]（最快陪同兩人各過一次）

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;  cin >> T;
    while (T--) {
        int n;  cin >> n;
        vector a(n);
        for (int &x : a) cin >> x;
        sort(a.begin(), a.end());

        long long ans = 0;
        while (n > 3) {
            long long cost1 = a[0] + 2LL*a[1] + a[n-1];
            long long cost2 = 2LL*a[0] + a[n-2] + a[n-1];
            ans += min(cost1, cost2);
            n -= 2;
        }
        if (n == 1) ans += a[0];
        else if (n == 2) ans += a[1];
        else if (n == 3) ans += a[0] + a[1] + a[2];
        cout << ans << "\n";
    }
    return 0;
}

複雜度與證明概要

• 時間 O(N log N)（排序主導），空間 O(N)。
• 貪心選擇性質：最慢兩人必須在某一輪一起過河，僅有上述兩種最優模式；交換論證可證局部最優推導全局最優。