P9518 题解

· · 题解

为啥要放模拟啊

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

先来考虑维护当前排队的人。我们需要一个支持 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} 左右，算是一道小清新模拟题。