# 題目: UVa 10172 - The Lonesome Cargo Distributor

# 題目說明

有一輛貨車跟數個站點,貨車與站點的容量有限制

貨車每到一個站會執行以下動作

  1. 將車上的貨物卸下,如果是目標貨物直接卸下,否則放到站點的 queue
  2. 將站點中的貨物裝到車上
  3. 移動到下一個站點

花費時間:

  1. 每次裝貨及卸貨都會花費 1 分鐘
  2. 移動到下一個站點會花費 2 分鐘

求所有貨物放到目標站點所花費的時間


INPUT:
第一行有一個整數 SET ,代表有幾筆資料
每筆資料的第一行有三個整數 NSQ
N 代表有幾站、 S 代表貨車可裝載貨物量、 Q 代表站點中 queue 的最大容量
接著有 N 行,從第 1 站至第 N 站
每行的第一個數字代表此站有幾個貨物,接著分別是貨物的目標編號


OUTPUT:
將所有貨物送到目標站點需要的分鐘數

# 解題方法

使用 stack 模擬貨車
vector< queue<int> > 模擬站點
接著跟著題目操作即可
stackvector< 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/