題目： UVa - 10901 - Ferry Loading III

題目說明

有一艘可以載車子的船，兩岸分別有一些要到達對岸的車子。船只有一艘，且一開始在左岸，當船目前所在的岸沒有車子，而對岸有車時，船必須直接過去載車，若是兩岸目前都沒有車，則船可以維持不動。而船上只要一有車就必須開到對岸，不可以等後面的車到達才開船。

Input： 第一行為一整數 T，代表有 T 組測資，每組測資第一行為三個整數 n, t, m，分別代表 船上能載的車子最大數量、船從一岸到達另一岸所需要的時間、需要過岸的車子數量。接下來 m 行，每行有一個整數及一個字串，整數代表車子到達岸邊的時間，字串只會為 "left" 或 "right" 代表車子到達的那個岸邊。

Output： 按照 Input 時車子的順序輸出車子到達對岸的時間。每組測資中間需以空行隔開。

解題思路

使用兩個 Queue 代表左岸及右岸，存放車子的編號 ( 代表順序 ) 及到達的時間。接著定義 time 為目前的時間，cur 為目前的位置 ( 0 為左岸，1 為右岸 )。每次執行時，先取得兩岸最先到達的車子的時間，接著更新 time，若是 time 變大代表在這段期間內船都在等車子到達，之後船就必須開到對岸了，因為不管先到達的是目前的岸還是對岸，船都必須開到對岸，開船前會將目前岸上的車子移到船上 ( 紀錄時間並直接 pop() 掉 )，最後更新 time 及 cur 即可。

參考解法

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <algorithm>
#include <climits>
#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 n, t, m;
        cin >> n >> t >> m;

        queue<pair<int, int>> bank[2]; // 0 for left, 1 for right
        vector<int> arriveTime(m);

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

        auto [time, cur] = make_pair(0, 0);
        while (!bank[0].empty() || !bank[1].empty())
        {
            int closest = INT_MAX;
            if (!bank[0].empty()) closest = bank[0].front().second;
            if (!bank[1].empty()) closest = min(closest, bank[1].front().second);

            time = max(time, closest);

            int cnt = 0;
            while (!bank[cur].empty() && cnt < n && bank[cur].front().second <= time)
            {
                arriveTime[bank[cur].front().first] = time + t;
                bank[cur].pop();
                ++cnt;
            }

            cur ^= 1;
            time += t;
        }

        for (auto& i : arriveTime) cout << i << '\n';
        if (T) cout << '\n';
    }
}

參考資料

UVa 10901 - Ferry Loading III.cpp