自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 22:49:08，当前版本为作者最后更新于2023-08-12 17:05:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为啥要放模拟啊

来理清思路我们要维护什么：

• 当前排队的人（按顺序）。
• 现在正在游玩的人。
• 每个人是否在排队/游玩。

先来考虑维护当前排队的人。我们需要一个支持 $O(\log n)$ 进行从尾部插入，并从任意位置删除元素的结构。这里我因为对 list 不熟悉而选择了 set：定义每个人的编号为当前队尾的人的编号 $+1$，为空时则是 $1$，即可保证人是有序的。

接下来定义两个 string->int\bool 的 map：inq（$\text{InQueue}$） 和 ing（$\text{InGame}$），分别表示每个人在队内的编号，以及是否在游玩。再用一个 string 数组 $t$ 以及一个 $num$ 来维护正在游玩的人与人数。我们就成功维护了所有需要的信息。定义大致如下：

struct node {
	string s; int id;
	bool operator < (const node &rhs) const { return id < rhs.id; }
}; set<node> q;

map<string, int> inq;
map<string, bool> ing;

分别来看三种操作：

arrive

如果目标处于对内或者正在游戏中，那么返回 0 表示 Error。否则按前文插入即可。

inline
bool try_insert(string s) {
	if (inq[s] || ing[s]) return 0;
	int x = q.empty() ? 0 : prev(q.end())->id;
	return q.insert({ s, inq[s] = x + 1 }), 1;
}

这里 prev(q.end())->id 的意思是查找 set 末尾这个人的编号。

leave

只需判断离开的人是否在队内。我们记录了每个人的编号，就能很方便的删除这个人。

inline
bool try_erase(string s) {
	if (!inq[s]) return 0;
	return q.erase({ s, inq[s] }), inq[s] = 0, 1;
}

start

分三步进行操作：

1. 将正在游玩的人清空，并且插入到当前队伍末端（使用 try_insert 完成）。
2. 确定游玩人数，如果队伍为空返回 Error。
3. 移除队伍前端需要游玩的人并储存到 t 数组中，更改正在游戏的状态（使用 try_erase 完成）并输出。

实现比较简单。

string t[2]; int num;

inline 
void try_start() {
	for (int i = 0; i < num; i++) ing[t[i]] = 0, try_insert(t[i]);
	num = min<int>(2, q.size());
	if (!num) return puts("Error"), void();
	for (int i = 0; i < num; i++) {
		try_erase(t[i] = q.begin()->s), ing[t[i]] = 1;
		cout << t[i] << " ";
	}
	puts("");
}

前两种操作根据返回值输出 OK 或 Error 即可。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;

struct node {
	string s; int id;
	bool operator < (const node &rhs) const { return id < rhs.id; }
}; set<node> q;

map<string, int> inq;
map<string, bool> ing;

inline
bool try_insert(string s) {
	if (inq[s] || ing[s]) return 0;
	int x = q.empty() ? 0 : prev(q.end())->id;
	return q.insert({ s, inq[s] = x + 1 }), 1;
}

inline
bool try_erase(string s) {
	if (!inq[s]) return 0;
	return q.erase({ s, inq[s] }), inq[s] = 0, 1;
}

string t[2]; int num;

inline 
void try_start() {
	for (int i = 0; i < num; i++) ing[t[i]] = 0, try_insert(t[i]);
	num = min<int>(2, q.size());
	if (!num) return puts("Error"), void();
	for (int i = 0; i < num; i++) {
		try_erase(t[i] = q.begin()->s), ing[t[i]] = 1;
		cout << t[i] << " ";
	}
	puts("");
}

int n; string opt, s;

int main() {
	for (scanf("%d", &n); n--;) {
		cin >> opt;
		if (opt[0] == 'a') cin >> s, puts(try_insert(s) ? "OK" : "Error");
		if (opt[0] == 'l') cin >> s, puts(try_erase(s) ? "OK" : "Error");
		if (opt[0] == 's') try_start();
	}
}

码量在 $1\text{KB}$ 左右，算是一道小清新模拟题。