Keep In Line

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

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 338ms, 内存消耗: 11404K, 提交时间: 2023-02-22 21:00:33

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		queue<string>a;
		map<string,int>b;
		string m,n;
		int q,sum;
		cin>>q;
		sum=q/2;
		while(q--){
		cin>>m>>n;
		while(!a.empty()&&b.count(a.front())){
		a.pop();}
		if(m=="in"){
			a.push(n);
		}
		else{
			b[n]=1;
			if(n!=a.front()){
			sum--;}
		}
	}
	cout<<sum<<endl;
	}
}

Python3 解法, 执行用时: 1740ms, 内存消耗: 8256K, 提交时间: 2022-02-23 16:28:42

t = int(input())
for _ in range(t):
    st = []
    n = int(input())
    ans = n//2
    for _ in range(n):
        cmd,name = input().split()
        if cmd == 'in':
            st.insert(0, name)
        else:
            if st[-1]!=name:
                st.remove(name)
                ans-=1
            else:
                st.pop()
    print(ans)

上一题

下一题

详情