P9518 queue 题解

· · 题解

前言

看没有使用 list 的题解，所以我发一篇使用 list 的题解。

我的代码没有使用数组，使用了很多 STL 中的容器（我觉得使用 STL 真的很方便）。

下面来具体讲一下我的思路。

思路

先说我的存储思路：

list<string> q;
unordered_set<string> us;
string a="",b="";
unordered_map<string,list<string>::iterator> um;

本题分为三种操作，我们分别来看。

第一种操作：start

首先我们判断队列是否为空，如果为空直接输出 Error，不继续进行后面的操作。

if(q.empty()){
    puts("Error");
    continue;
}

接着，新一局游戏的开始代表着正在玩的人需要到队尾重新排队，等待下一次游玩。但有可能有两个人在玩，也有可能没有人在玩，这里就需要特殊判断一下了。思路是先把两个（也有可能是一个）人加入队尾，然后再把队头的两个（或一个）人从队头（游戏机座位上）弹出。这里要重新记录一下当前这个人在链表中对应的地址。

if(a!=""){
    q.push_back(a),q.pop_front();
    um[a]=--q.end();
}
if(b!=""){
    q.push_back(b),q.pop_front();
    um[b]=--q.end();
}

然后，获取新一局的玩家。先获取第一个人，然后判断是否还有第二个人，没有第二个人那么将记录第二个人名字的字符串设为空。

a=q.front();
q.pop_front();
if(!q.empty()){
    b=q.front();
}else{
    b="";
}

因为要根据队列是否为空这个条件来判断有没有第二个玩游戏的人，因此我们要把第一个人从队列里先弹出，然后再加到队首。这里要重新记录一下当前这个人在链表中对应的地址。

q.push_front(a);
um[a]=q.begin();

最后输出即可。

cout<<a;
if(b!="")cout<<" "<<b;
cout<<endl;

第二种操作：arrive

首先输入到达的人的名字。

string k;
cin>>k;

接下来，通过 unordered_set，找到里面是否已经有这个人了。如果已经有了，那么输出 Error。

if(us.find(k)!=us.end()){
    puts("Error");
    continue;
}

将这个人加到队尾并加入 unordered_set 当中。注意，要重新记录这个人在链表中对应的地址。这里 q.end() 是获取 list 最后一个元素后面一个位置的地址，但不是最后一个元素的，因此要 --q.end()。为什么不是 -1 呢？因为只重载了 -- 这个运算符。接着，输出 OK 即可。

q.push_back(k);
um[k]=--q.end();
us.insert(k);
puts("OK");

第三种操作：leave

这个操作就体现了使用 list 的好处。

首先输入要离开的人的名字。

string k;
cin>>k;

接着，如果要离开的人正在玩游戏机或者找不到这个人，输出 Error。

if(k==a||k==b||us.find(k)==us.end()){
    puts("Error");
    continue;
}

最后，从 list 和 unordered_set 之中删除掉这个人，然后输出 OK 即可。注意我们之前记录了每个人在链表中对应的地址，所以直接拿过来用就好了。无论是查找地址还是删除，都是 \mathcal{O}(1) 的。

q.erase(um[k]);
us.erase(us.find(k));
puts("OK");

代码

最后放上完整代码：

#include <bits/stdc++.h>
using namespace std;
list<string> q;
string a="",b="";
unordered_set<string> us;
unordered_map<string,list<string>::iterator> um;
int main(){
    int n;
    cin>>n;
    while(n--){
        string s;
        cin>>s;
        if(s=="start"){ // 新一局开始。
            if(q.empty()){  // 当前没有人排队。
                puts("Error");
                continue;
            }
            if(a!=""){
                q.push_back(a),q.pop_front();   // 加到队尾，并删除队首元素。
                um[a]=--q.end();    // 记录这个人在链表中对应的地址。
            }
            if(b!=""){
                q.push_back(b),q.pop_front();   // 同上。
                um[b]=--q.end();    // 同上。
            }
            a=q.front();
            q.pop_front();
            if(!q.empty()){ // 有可能一开始排队人数只有一个人（弹出去以后链表中就没有元素了），没法两个人一起玩。
                b=q.front();
            }else{
                b="";   // 如果只有一个人能玩，那么将记录第二个人名字的字符串设为空。
            }
            q.push_front(a);    // 将正在玩游戏的人添加到队首（之前为了要根据队列是否为空这个条件来判断有没有第二个玩游戏的人，因此将第一个人从队列里先弹出，然后再加到队首）。
            um[a]=q.begin();    // 记录地址。
            cout<<a;    // 输出。
            if(b!="")cout<<" "<<b;
            cout<<endl;
        }else if(s=="arrive"){  // 第二种操作。
            string k;
            cin>>k; // 先输入。
            if(us.find(k)!=us.end()){   // 如果以前有这个元素，那么输出“Error”。
                puts("Error");
                continue;
            }
            q.push_back(k); // 入队。
            um[k]=--q.end();    // 记录地址。
            us.insert(k);   // 加入集合。
            puts("OK");
        }else if(s=="leave"){   // 第三种操作。
            string k;
            cin>>k;
            if(k==a||k==b||us.find(k)==us.end()){   // 如果正在游玩或者这个人根本就没在排队，那么输出“Error”。
                puts("Error");
                continue;
            }
            q.erase(um[k]); // 删除掉这个人。
            us.erase(us.find(k));   // 同上。
            puts("OK");
        }
    }
    return 0;
}

这里是 AC 记录。

谢谢大家！