牛客竞赛算法入门题单打卡 J Keep in Line

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
?

题目描述

又到饭点了，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

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

输出

复制2

2

思路

队列的题目，对于每次操作，in则将他们入队，out则将他们的名字与队首的名字作比较，如果相同，则代表没插队，如果不同，分为没插队但名字被插队的人排在前面和插队两种情况，第一种情况下，将插队的人名字先出队，再进行比较，如果相同则没插队，总数加一

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		map<string,int>mp;//mp用于记录每个人是否出队
		queue<string>q;
		int ans=0;
		string opt,name;
		for(int i=0;i<n;i++)
		{
			cin>>opt;
			cin>>name;
			if(opt=="in")
			{
				q.push(name);
				mp[name]=0;//0表示在队伍1表示出去了
			}
			else{
				if(q.front()!=name)//一种是没出去过，插队，一种是名字被插队的挤了
				{
					while(mp[q.front()]==1)//名字被插队的挤了
					{
						q.pop();
					}
					if(q.front()==name)//没插队，则总数加一
					{
						ans++;
					}mp[name]=1;
				}
				else {
					ans++;
					q.pop();
					mp[name]=1;
				}	
			}
		}
		cout<<ans<<endl;
	}
}