NC13822 Keep In Line

题目

题目描述

又到饭点了，SK同学靠着惯性走到了食堂，但长长的队伍顿时让他失去了食欲。突然，他注意到某个窗口前的队伍里明显存在插队的现象，于是他默默记录下了同学们进队和出队的变化。

对于进队，SK同学只知道队伍里多了一个人，并不知道新来的人是老老实实站到了队尾还是插到了队伍里的某个位置；对于出队，SK同学能确定是队伍里站在最前面的人出队了。

初始时队伍为空，给出 \(n\) 条队伍进出的信息，保证已经出队的同学不会再入队，并且最终队伍也为空，现在SK同学想知道有多少不插队的好同学。

输入描述

第一行是一个正整数 \(T(≤ 5)\) ，表示测试数据的组数， 对于每组测试数据， 第一行是一个整数 \(n(1≤ n ≤ 100000)\) ，表示这个队伍进出的信息数， 接下来 \(n\) 行，每行是两个字符串Opt Name，其中Opt为"in"代表进队，"out"代表出队，Name为进队或出队的人的名字， 所有信息按照时间顺序给出，名字由英文字母和阿拉伯数字组成，长度不超过 \(10\) ，保证每个人的名字各不相同。

输出描述

对于每组测试数据，输出一行，包含一个整数，表示不插队的人数。

示例1

输入

1
6
in quailty
in hwq1352249
out hwq1352249
in zhuaiballl
out quailty
out zhuaiballl

输出

2

题解

思路

知识点：队列。

队列具有不改变排列顺序的性质。如果是不插队排队，则 in 的顺序即理想 out 队列。现在按照实际 out 的队列 \(q_2\) 与理想的 out 队列 \(q_1\)对比，因为不插队的人的实际顺序和理想顺序的相对位置不会改变，而插队的人会和理想顺序错位，且第一个人一定不插队，所以用 \(q2\) 的人从 \(q1\) 的第一个人开始匹配。

若 \(q2\) 的队首与 \(q1\) 队首匹配，说明找到一个不插队的人，计数加一 。

每次都将 \(q2\) 这次匹配的人标记，先弹出 \(q2\) ，若这次匹配则会将这次匹配到的人以及后面之前 \(q2\) 标记过的（插过队的）人从 \(q1\) 中弹出，直到队空或者没有标记（没插队），否则 \(q1\) 不变。

用 \(unordered\_map\) 存入字符串到布尔的映射，表示访问情况。

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;


bool solve() {
    int n;
    cin >> n;
    unordered_map<string, bool> mp;
    queue<string> q1, q2;
    while (n--) {
        string op, name;
        cin >> op >> name;
        if (op == "in") q1.push(name);
        else if (op == "out") q2.push(name);
    }
    int cnt = 0;
    while (!q2.empty()) {
        if (q1.front() == q2.front())cnt++;
        mp[q2.front()] = 1;
        while (!q1.empty() && mp[q1.front()]) q1.pop();
        q2.pop();
    }
    cout << cnt << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}