Escalator（模拟队列）

题意

有一群人要坐电梯，有的想上去，有的想下来，上去和下来都要花费 10 分钟时间，同一方向的人可以在电梯未停止时就上去，不同方向的人必须在电梯停止时才能上电梯，求最后一个人离开电梯的时间

思路

模拟 2 个队列，分别代表 2 个方向的人，同一方向的人到达电梯在电梯运行结束之前上去，否则电梯停止运行，比较 2 个队列最先到达的人，谁先到电梯就往那个方向运行

代码

#include <iostream>
#include <algorithm>
#include <queue>
typedef long long ll;
using namespace std;
#define endl '\n'
// 没必要用优先队列，因为题目规定了顺序从小到大
priority_queue<int, vector<int>, greater<int> > p, q;
int main() {
    int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		if (y) p.push(x);
		else q.push(x);
	}
	int ans = 0;
	while (!p.empty() && !q.empty()) {
		if (p.top() < q.top()) {
			// ans 比 p.top() 大，代表反方向的电梯尚未停止运行，要等它停止运行了才能上电梯
			// 否则，代表电梯停止运行时，队列 p 的第一个人还没到达
			ans = max(ans, p.top()) + 10;// 电梯预计停止运行时间
			p.pop();
			// 如果还有向左的人并且向左的人中最快到达的人在电梯停止运行之前到达
			while (!p.empty() && p.top() < ans) {
				// 如果向左的人中最快到达的人超出了原来的电梯预计停止运行时间，就更新电梯预计停止运行时间
				if (p.top() + 10 > ans) ans = p.top() + 10;
				// 向左的人中最快到达的人上了电梯，将他从队列中移除
				p.pop();
			}
		} else {
			ans = max(ans, q.top()) + 10;
			q.pop();
			while (!q.empty() && q.top() < ans) {
				if (q.top() + 10 > ans) ans = q.top() + 10;
				q.pop();
			}
		}
	}
    // 在电梯停止运行之前，所有人都到了，他们一起乘坐一趟 10 分钟的电梯
	if (!p.empty()) ans = max(p.top(), ans) + 10, p.pop();
	else ans = max(q.top(), ans) + 10, q.pop();
	// _ans 如果电梯停止运行了，还有人没到
	int _ans = 0;
	// 更新尚未空的队列
	while (!p.empty()) _ans = p.top() + 10, p.pop();
	while (!q.empty()) _ans = q.top() + 10, q.pop();
	cout << max(ans, _ans) << endl;
	return 0;
}