0%

牛客 13822 Keep In Line(枚举与暴力、Python)

链接:https://ac.nowcoder.com/acm/problem/13822
来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

又到饭点了,SK同学靠着惯性走到了食堂,但长长的队伍顿时让他失去了食欲。突然,他注意到某个窗口前的队伍里明显存在插队的现象,于是他默默记录下了同学们进队和出队的变化。
对于进队,SK同学只知道队伍里多了一个人,并不知道新来的人是老老实实站到了队尾还是插到了队伍里的某个位置;对于出队,SK同学能确定是队伍里站在最前面的人出队了。
初始时队伍为空,给出n条队伍进出的信息,保证已经出队的同学不会再入队,并且最终队伍也为空,现在SK同学想知道有多少不插队的好同学。

输入描述:

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

输出描述:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例1

输入
1
6
in quailty
in hwq1352249
out hwq1352249
in zhuaiballl
out quailty
out zhuaiballl

输出
2
1
2
3
4
首先建一个队列,里面按照入队顺序存放字符串。
然后等读入出队信息的时候,如果出队是正常出队,ans++,就直接删除队首元素,
如果不是正常出队,并利用map标记此字符串为1,遇到队首元素标记为1的直接出队。
最后输出ans。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
T = int(input())

for i in range(T):
n = int(input())
queue = []
jumpers = {}
ans = 0
for j in range(n):
s = input().split(" ")
if s[0] == 'in':
queue.append(s[1])
else:
while queue[0] in jumpers:
del queue[0]
if queue[0] != s[1]:
jumpers[s[1]] = 1
else:
del queue[0]
ans += 1
print(ans)
-------------    本文结束  感谢您的阅读    -------------