# 題目: UVa 10172 - The Lonesome Cargo Distributor
# 題目說明
有一輛貨車跟數個站點,貨車與站點的容量有限制
貨車每到一個站會執行以下動作
- 將車上的貨物卸下,如果是目標貨物直接卸下,否則放到站點的
queue
中 - 將站點中的貨物裝到車上
- 移動到下一個站點
花費時間:
- 每次裝貨及卸貨都會花費 1 分鐘
- 移動到下一個站點會花費 2 分鐘
求所有貨物放到目標站點所花費的時間
INPUT:
第一行有一個整數 SET
,代表有幾筆資料
每筆資料的第一行有三個整數 N
、 S
、 Q
N
代表有幾站、 S
代表貨車可裝載貨物量、 Q
代表站點中 queue
的最大容量
接著有 N
行,從第 1 站至第 N 站
每行的第一個數字代表此站有幾個貨物,接著分別是貨物的目標編號
OUTPUT:
將所有貨物送到目標站點需要的分鐘數
# 解題方法
使用 stack
模擬貨車
以 vector< queue<int> >
模擬站點
接著跟著題目操作即可
當 stack
及 vector< queue<int> >
皆為空時,此筆測資結束
# 參考程式碼
#include <iostream> | |
#include <stack> | |
#include <queue> | |
#include <vector> | |
using namespace std; | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
cout.tie(nullptr); | |
int SET, N, S, Q, Qi, temp; | |
cin >> SET; | |
while (SET--) { | |
stack<int> carrier; | |
vector< queue<int> > stations; | |
cin >> N >> S >> Q; | |
for (size_t i = 0; i < N; ++i) { | |
queue<int> station; | |
cin >> Qi; | |
for (size_t j = 0; j < Qi; ++j) cin >> temp, station.emplace(temp - 1); | |
stations.emplace_back(station); | |
} | |
int cur = 0, time = 0; | |
while (1) { | |
while (!carrier.empty() && (carrier.top() == cur || stations[cur].size() < Q)) { | |
if (carrier.top() != cur) stations[cur].emplace(carrier.top()); | |
carrier.pop(); | |
++time; | |
} | |
while (!stations[cur].empty() && carrier.size() < S) { | |
carrier.emplace(stations[cur].front()); | |
stations[cur].pop(); | |
++time; | |
} | |
bool out = true; | |
for (size_t i = 0; i < N; ++i) | |
if (!stations[i].empty() || !carrier.empty()) { | |
cur = ++cur % N; | |
time += 2; | |
out = false; | |
break; | |
} | |
if (out) break; | |
} | |
cout << time << "\n"; | |
} | |
return 0; | |
} |
# 參考資料
https://www.larrysprognotes.com/UVa%20-%2010172/