# 題目: UVa 10901 - Ferry Loading III

# 題目說明

有車子想要渡河，目前唯一渡河的方式為搭船
船只有一艘且容量有限，求所有車子到達對岸的時間

---

INPUT:
第一行有一個整數c，代表有c筆資料
每筆測資第一行有三個整數n、t、m

1. n代表船能容納的車子數量
2. t代表船開到對岸的時間
3. m代表等待過河的車子數量
   接下來有m行，每行有一個整數和一個字串，整數代表車子到岸邊的時間，字串代表它處於河的哪一邊

---

OUTPUT:
輸出每輛車子到達對岸的時間
每筆資料以空行隔開

# 解題方法

以兩個queue分別存左岸及右岸的車子，存順序及到達時間
接著跑迴圈直到兩個queue都為空

• 如果左岸為空，船直接移動到右岸
• 如果右岸為空，船直接移動到左岸
• 如果皆不為空，則判斷最早到的車子並移動到相應的岸邊

# 參考程式碼

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int c;
	cin >> c;

	while (c--) {

		int n, t, m, in;
		string side;
		pair<int, int> temp;
		queue< pair<int, int> > boatl, boatr;

		cin >> n >> t >> m;	
		for (size_t i = 0; i < m; ++i) {		
			cin >> temp.first >> side;
			temp.second = i;
			side == "left" ? boatl.emplace(temp) : boatr.emplace(temp);
		}

		int time = 0;
		auto cur = &boatl;
		vector<int> result(m);
		while (!boatl.empty() || !boatr.empty()) {

			if (boatr.empty()) {			
				time = max(time, boatl.front().first);
				if (*cur == boatr) time += t, cur = &boatl;
			}
			else if (boatl.empty()) {
				time = max(time, boatr.front().first);
				if (*cur == boatl) time += t, cur = &boatr;
			}
			else {
				auto small = (boatl.front().first < boatr.front().first) ? &boatl : &boatr;
				if (boatl.front().first == boatr.front().first) small = cur;

				if (time >= small->front().first) {
					if (small != cur && time < cur->front().first)
						time += t, cur = small;
				}
				else {
					time = small->front().first;
					if (small != cur) time += t, cur = small;				
				}
			}

			for (size_t i = 0; i < n && !cur->empty(); ++i)
				if (cur->front().first <= time) result[cur->front().second] = time + t, cur->pop();
			time += t;
			if (*cur == boatl) cur = &boatr;
			else cur = &boatl;
		}

		for (auto& i : result) cout << i << "\n";
		if(c) cout << "\n";
	}

	return 0;
}

# 程式碼(修正版)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef tuple<int, int, int> tp;
typedef pair<int, int> p;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T;
	cin >> T;
	
	while (T--)
	{
		int n, t, m;
		queue<p> Q[2];

		cin >> n >> t >> m;

		for (int i = 0; i < m; ++i)
		{
			int time;
			string side;

			cin >> time >> side;
			side == "left" ? Q[0].push({ time, i }) : Q[1].push({ time, i });
		}

		int cur = 0, time = 0;
		vector<int> ret(m);
		while (!Q[0].empty() || !Q[1].empty())
		{
			int close, cnt = 0;

			if (Q[0].empty()) close = Q[1].front().first;
			else if (Q[1].empty()) close = Q[0].front().first;
			else close = min(Q[1].front().first, Q[0].front().first);
			time = max(time, close);

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

			cur ^= 1;
			time += t;
		}

		for (auto& i : ret) cout << i << "\n";
		if (T) cout << "\n";
	}
}

# 參考資料

https://www.larrysprognotes.com/UVa%20-%2010901/