題目： UVa - 11034 - Ferry Loading IV

題目說明

有一艘可以載車子的船，兩岸分別有一些要到達對岸的車子，船有長度限制，在不超過船的長度限制的前提下，要放多少輛車都可以。在岸邊的車子有先後順序之分，在載完前面的車子前，不可以載後面的車子。

Input： 第一行為一個整數 T，代表有 T 組測資，每組測資第一行為兩個整數 l, m，分別代表 船的長度 ( 船的長度的單位為車子長度的單位的一百倍 ) 及 需要過岸的車子數量，接下來 m 行，每行有一個整數及一個字串，整數代表車子的長度，字串只會為 "left" 或 "right" 代表車子所在的那個岸邊。

Output： 求將所有車子都移到各自的對岸，船需要走幾趟 ( 來回算兩趟 )。

解題思路

使用兩個 Queue 代表左岸及右岸，儲存車子的長度，之後模擬操作即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <queue>

using namespace std;

// reference: https://ppt.cc/fNbc8x

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        int l, m;
        cin >> l >> m;

        // 0 for left, 1 for right
        queue<int> bank[2];

        auto [tmp, str] = make_pair(0, string());
        for (int i = 0; i < m; ++i)
        {
            cin >> tmp >> str;
            str == "left" ? bank[0].push(tmp) : bank[1].push(tmp);
        }

        int cnt = 0, cur = 0;
        while (!bank[0].empty() || !bank[1].empty())
        {
            int Cap = l * 100;
            while (!bank[cur].empty() && bank[cur].front() <= Cap)
                Cap -= bank[cur].front(), bank[cur].pop();
            cur ^= 1;
            ++cnt;
        }

        cout << cnt << '\n';
    }
}

參考資料

UVa 10901 - Ferry Loading III.cpp