題目： UVa - 10172 - The Lonesome Cargo Distributor

題目說明

有一台卡車及一個環形公路，公路上有許多站點，每個站點會有一個地方放要送到這個站點的貨物，還有一個要到其他站點的 Queue，所有站點的 Queue 都會有相同的容量限制，卡車的結構類似於 Stack，在移除上面的貨物前，無法移動下面的貨物。卡車每到一個站後都會執行相同的事情：

  1. 先將車上的貨物卸下，若是目前的站點是貨物要到達的站點的話則直接卸下，否則放入該站點的 Queue 的尾端，重複執行直到貨車為空或是該站點的 Queue 已滿。
  2. 將站點的 Queue 中的貨物從前端開始放到卡車上，直到卡車滿或是 Queue 為空。
  3. 移動到下一個站點。

重複以上的動作直到所有貨物都到達該到達的站點為止。

  1. 卡車每次卸貨或裝貨都會花費一分鐘。
  2. 卡車每次移動到下個站點都會花費兩分鐘。

Input： 第一行為一整數，代表接下來有幾組測資。每組測資的第一行有三個整數 n、s、q，分別代表 站點的數量、貨車的最大容量、站點中 Queue 的最大容量。接下來會有 n 行，代表站點的資訊，從第一個站點開始依序往下。每行起始於一個整數，代表 Queue 中有幾個貨物，後面有該數量個數字，代表每個貨物該到達的站點 ( 不會有要到達目前站點的貨物 )。

Output： 輸出將所有貨物都送達該送達的站點所需要花費的時間 ( 分鐘 )。

解題思路

使用 Stack 模擬卡車，Queue 陣列模擬站點即可，由於 (2 ≤ n ≤ 100)，所以將陣列大小設為 100。

先輸入所有資料，並存入對應的 Queue，接著根據題目操作即可。先將 Stack 裡面的資料 pop() 出來，若是目前站點不是貨物要到達的站點則將貨物放 Queue 的尾端，做完後再把 Queue 中的貨物從前端開始放入 Stack，最後判斷卡車及所有 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <stack>
#include <queue>

using namespace std;

// reference: https://ppt.cc/fIHBVx

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

int main()
{
    int n, s, q;
    int T;
    cin >> T;
    while (T--)
    {
        stack<int> truck;
        queue<int> stationQueue[100];

        cin >> n >> s >> q;

        for (int i = 0; i < n; ++i)
        {
            int nc;
            cin >> nc;
            for (int j = 0; j < nc; ++j)
            {
                int target;
                cin >> target;
                stationQueue[i].push(target - 1);
            }
        }

        int cur = 0, time = 0;
        auto unload = [&]
        {
            return (!truck.empty() &&
                (truck.top() == cur || stationQueue[cur].size() < q));
        };

        while (true)
        {
            while (unload())
            {
                if (truck.top() != cur) stationQueue[cur].push(truck.top());
                truck.pop();
                ++time;
            }

            while (truck.size() < s && (!stationQueue[cur].empty()))
            {
                truck.push(stationQueue[cur].front());
                stationQueue[cur].pop();
                ++time;
            }

            bool clear = truck.empty();
            for (int i = 0; i < n && clear; ++i) clear &= stationQueue[i].empty();

            if (clear) break;

            cur = (cur + 1) % n;
            time += 2;
        }
        cout << time << '\n';
    }
}

參考資料

Unfortunate狗的ACM園地: 10172 - The Lonesome Cargo Distributor
UVa 10172 - The Lonesome Cargo Distributor.cpp