POJ 3282 Ferry Loading IV：渡輪裝車模擬與貪心策略

POJ 3282 Ferry Loading IV：簡單模擬求渡河次數

題目描述一條長度為 l 米的渡輪，在左右兩岸來回穿梭載運汽車。汽車按到達順序排隊，渡輪每次盡可能裝載當前岸邊的車輛（總長度不超過渡輪長度），直到所有車輛運送完畢。求渡輪最少過河次數。

解題思路：

• 使用兩個佇列分別存放左岸和右岸等待車輛的長度（單位：厘米）。
• 渡輪初始在左岸（d = 1 表示左岸，-1 表示右岸）。
• 每次從當前岸邊的佇列中依序裝車，直到無法裝下下一輛車或佇列為空。
• 裝完後渡河（d = -d），次數 num++。
• 重複直到兩岸佇列皆空。

注意：渡輪長度 l 為米，車長為厘米，裝載時需統一單位（sum = len * 100）。

參考代碼（C++）：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

int main() {
    int t, len, n;
    scanf("%d", &t);
    while (t--) {
        queue<int> l, r;
        scanf("%d%d", &len, &n);
        for (int i = 0; i < n; i++) {
            int x; char str[15];
            scanf("%d%s", &x, str);
            if (str[0] == 'l') l.push(x);
            else r.push(x);
        }
        int d = 1, num = 0;
        while (!l.empty() || !r.empty()) {
            int sum = len * 100, s = 0;
            if (d == 1) {
                while (!l.empty() && s + l.front() <= sum) { s += l.front(); l.pop(); }
            } else {
                while (!r.empty() && s + r.front() <= sum) { s += r.front(); r.pop(); }
            }
            d = -d;
            num++;
        }
        printf("%d\n", num);
    }
    return 0;
}

本題考察基本模擬能力與細節處理（單位換算、佇列操作、邊界條件），是入門級模擬題的好範例。