POJ 3282 Ferry Loading IV：雙隊列模擬渡輪裝車

問題描述

渡輪長度 l 米，初始在左岸。m 輛車按到達順序給出長度（厘米）和岸邊。渡輪每次航行裝載當前岸邊隊列中盡可能多的車（先到先裝，總長 ≤ l×100），然後過河卸車。求將所有車運完所需的最少過河次數。

解法：獨立計算兩岸所需航次

關鍵觀察：渡輪必須交替在兩岸裝車。左岸車只能在左岸裝，右岸車只能在右岸裝。因此，左岸車需要的航次 L 和右岸車需要的航次 R 可以獨立計算：

• 對左岸隊列，貪心裝載：每次盡可能多裝，計數 L。
• 對右岸隊列，同理計數 R。

總過河次數：

• 若 L > R：渡輪最後一次在左岸裝車後過河到右岸結束，共 2*L - 1 次。
• 若 L ≤ R：最後一次在右岸裝車結束，共 2*R 次。

模擬邏輯

int calc(queue<int>& q, int cap) {
    int trips = 0, load = 0;
    while (!q.empty()) {
        load = 0;
        while (!q.empty() && load + q.front() <= cap) {
            load += q.front(); q.pop();
        }
        trips++;
    }
    return trips;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int l, m; scanf("%d%d", &l, &m);
        queue<int> left, right;
        for (int i = 0; i < m; i++) {
            int len; char side[10];
            scanf("%d%s", &len, side);
            (side[0] == 'l' ? left : right).push(len);
        }
        int L = calc(left, l * 100);
        int R = calc(right, l * 100);
        printf("%d\n", L > R ? 2*L - 1 : 2*R);
    }
    return 0;
}

複雜度

• 時間：O(m)，每輛車進出隊列一次。
• 空間：O(m) 存儲隊列。

總結

本題看似需要模擬渡輪往返，實則兩岸獨立。貪心裝載（先到先裝、盡可能多裝）得到各岸最少航次，再根據誰多誰少推導總次數。代碼極其簡潔，是模擬題中「化繁為簡」的典範。