P9518 queue

Flanksy · 2023-08-13 13:27:58 · 题解

模拟

2023/8/16：感谢 xing_yu 和 hhyz100413 告知代码被 hack，现已修复。

看一眼题目，鉴定为维护序列，分析一下操作。

• 将被标记的元素移动到队尾并取消标记，标记并输出当前序列第一个或前两个元素，要求序列不空。
• 在队尾加入元素，要求元素不能已经在序列中。
• 删除任意元素，要求元素在序列中且没有被标记。

可以发现一个关键性质：序列元素不重。

由于元素不重，链表可以做到 O(1) 查找，记录每个元素的位置即可。同时链表自身 O(1) 插入删除的特性也很优秀。

不想手写链表的话，list 是一个很好的选择。

使用 unordered_map 记录每个元素是否存在和每个元素在 list 中对应的迭代器，注意将元素从队首扔到队尾的时候需要更新。

被 hack 实际是因为读错题目。认为队列的前两位始终保持游玩状态是错误的，只有最近一次 start 时的队首才处于游玩状态，因此需要记录当前正在游玩者的个数用于判断，即被标记的元素个数。

先前代码中已经使用变量记录当前游玩人数，只在原有基础上做了轻微的改动。

时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
unordered_map<string,list<string>::iterator> ex;
unordered_map<string,bool> on;
list<string> q;
int last_sum;//从 start 函数内的静态变量改为全局变量 
void arrive(){
    static string x;
    cin>>x;
    if(on[x]) return cout<<"Error"<<'\n',void();
    on[x]=1,q.push_back(x);
    ex[x]=prev(q.end());
    cout<<"OK"<<'\n';
}
void start(){
    static bool started;
    if(q.empty()) return cout<<"Error"<<'\n',void();
    if(started) for(int i=1;i<=last_sum;i++){
        q.push_back(q.front());
        ex[q.front()]=prev(q.end());
        q.pop_front();
    }
    started=1;
    if(q.size()==1u) last_sum=1,cout<<q.front()<<'\n';
    else last_sum=2,cout<<q.front()<<' '<<*next(q.begin())<<'\n';
}
bool isplaying(string x){//新添加的函数 
    auto it=q.begin();
    for(int i=1;i<=last_sum;i++){
        if(it==q.end()) break;
        if(*it++==x) return 1;
    }
    return 0;
}
void leave(){
    static string x;
    cin>>x;
    if(!on[x]||isplaying(x)) return cout<<"Error"<<'\n',void();
    on[x]=0,q.erase(ex[x]);
    cout<<"OK"<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        static string x;
        cin>>x;
        switch(x[0]){
            case 'a':arrive();break;
            case 's':start();break;
            case 'l':leave();break;
        }
    }
    return 0;
}