洛谷 P9518 queue

一眼模拟。

需要维护的东西可以根据操作求得：

• start：正在玩游戏的 \(1\) 或 \(2\) 个人；
• arrive：当前在排队但没玩游戏的队列、每个人是否在排队、游玩；
• leave：每个人是否在排队、游玩。

如何维护

正在玩游戏的人：

我们使用 \(p_1\)、\(p_2\) 两变量存储，优先保证 \(p_1\) 有值，当 \(p_1\) 为空时上一轮无人游玩，\(p_2\) 为空时上一轮仅有一人游玩。

tips：由于优先保证 \(p_1\) 有值，故 \(p_2\) 为空时 \(p_1\) 非空。

当前在排队但没玩游戏的队列：

用数组模拟队列并惰性删除即可。

tips：将正在玩游戏的人放到队首，并在玩完游戏后将其放到队尾，只用维护一个“队列”即可。

每个人是否在排队、游玩：

用 map 映射名字到队列中的位置即可（tips：为什么不映射 bool，在这个讨论帖里说的已经很明白了）。

要定义的东西如下：

const int Maxn = 1e6 + 7;
int Q, l = 1, r = 1, len;
string q[Maxn], p1, p2;
map <string, int> m;

操作中的细节

start

只要队列里有人，游戏就能进行。因为根据题意描述，若只有 A 在游戏且无人排队、A 可在结束游戏后成为队首并加入下一轮游戏，故队列无人时输出 Error。

否则，将上一轮游玩的人放回队尾，并取出这一轮游玩的人（\(\geq 1\)，想一想，为什么），将其名字输出。

具体实现如下：

if(opt == "start") {
	p1 = p2 = "";
	while(l < r && len) {
	    while(l < r && m[q[l]] != l) ++l;
	    if(l < r)
	    	m[q[l]] = r, q[r++] = q[l], ++l;
	    --len;
	}

	while(l < r && m[q[l]] != l)
		++l;
	if(l == r) {
		puts("Error");
		continue;
	}
	p1 = q[l]; 
    cout << p1;
	++len;
	   
	int pos = l + 1;
    while(pos < r && m[q[pos]] != pos) 
		++pos;
    if(pos < r) 
		p2 = q[pos], cout << ' ' << p2, ++len;
    puts("");
}

arrive

没什么好说的，看代码：

if(opt == "arrive") {
	cin >> t;
	if(m[t]) 
		puts("Error");
	else 
		q[r++] = t, m[t] = r - 1, puts("OK"); 
}

leave

若 x 在队列里且 x 不为玩家，x 可以离队；否则不能。

if (opt == "leave") {
	cin >> t;
	if(m[t] && t != p1 && t != p2) 
		m[t] = 0, puts("OK");
	else 
		puts("Error");
}

Warning

考场并没有卡暴力 \(O(n)\) 删除的做法，但考试结束后同机房的 @幻想繁星 就申请加了 hack 数据（试图卡掉时的讨论帖、hack 数据）

Talk is cheap, show you the code.

#include <bits/stdc++.h>

using namespace std;
const int Maxn = 1e6 + 7;

int Q, l = 1, r = 1, len;
string q[Maxn], p1, p2;
map <string, int> m;

int main() {
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	cin >> Q;
	string opt, t;
	while(Q--) {
		cin >> opt;
		if(opt == "start") {
			p1 = p2 = "";
            while(l < r && len) {
                while(l < r && m[q[l]] != l) ++l;
                if(l < r)
                	m[q[l]] = r, q[r++] = q[l], ++l;
                --len;
            }

            while(l < r && m[q[l]] != l)
				++l;
            if(l == r) {
				puts("Error");
				continue;
			}
			p1 = q[l]; 
            cout << p1;
			++len;
            
			int pos = l + 1;
            while(pos < r && m[q[pos]] != pos) 
				++pos;
            if(pos < r) 
				p2 = q[pos], cout << ' ' << p2, ++len;
            puts("");
		}
		else if(opt == "arrive") {
			cin >> t;
			if(m[t]) 
				puts("Error");
			else 
				q[r++] = t, m[t] = r - 1, puts("OK"); 
		}
		else {
			cin >> t;
			if(p1 == t || p2 == t || !m[t]) 
				puts("Error");
			else 
				m[t] = 0, puts("OK");
		}
	}
	
	return 0;
}