MT2021-10-3公司食堂

小美和小团所在公司的食堂有N张餐桌，从左到右摆成一排，每张餐桌有2张餐椅供至多2人用餐，公司职员排队进入食堂用餐。小美发现职员用餐的一个规律并告诉小团：当男职员进入食堂时，他会优先选择已经坐有1人的餐桌用餐，只有当每张餐桌要么空着要么坐满2人时，他才会考虑空着的餐桌；

当女职员进入食堂时，她会优先选择未坐人的餐桌用餐，只有当每张餐桌都坐有至少1人时，她才会考虑已经坐有1人的餐桌；

无论男女，当有多张餐桌供职员选择时，他会选择最靠左的餐桌用餐。现在食堂内已有若干人在用餐，另外M个人正排队进入食堂，小团会根据小美告诉他的规律预测排队的每个人分别会坐哪张餐桌。

///这个题必须用scanf和printf,否则超时
//cin的编译时间大约是scanf的3~4倍。所以，在使用大量数据的时候，cin的运算速度明显要满于scanf。

#include<iostream>
#include<vector>
#include<string>
#include<queue>///priority_queue默认为less<int>最大堆，小根堆greater<int>
#include<functional>///greater<int>的头文件
using namespace std;

int N;
//int seat[500005];
char seat;
int M;
char MF;

int main()
{
	int T;
	//cin>>T;
	scanf("%d", &T);
	priority_queue<int, vector<int>, greater<int> > q0;//表示有0个人的座位下标
	priority_queue<int, vector<int>, greater<int> > q1;//表示有一个人的座位下标
	//int seat[500005];
	while (T--)
	{
		
		//cin >> N;
		scanf("%d", &N);

		while (!q0.empty())
			q0.pop();
		while (!q1.empty())
			q1.pop();
		//string seat;
		//seat.resize(N);
		//scanf("%s", &seat[0]);//scanf没办法输入string，需要resize,%s  &seat[0]

		getchar();///getchar()是在输入缓冲区顺序读入一个字符(包括空格、回车和Tab)
		for (int i = 0; i < N; ++i)
		{
			scanf("%c", &seat);
			if (seat == '0')
				q0.push(i);
			else if (seat== '1')///这里是字符串
				q1.push(i);
		}
		
		scanf("%d", &M);
		
		///MF.resize(M);
		///scanf("%s", &MF[0]);
		getchar();
		for (int i = 0; i < M; ++i)
		{
			scanf("%c", &MF);
			if (MF == 'M')//男士
			{
				if (!q1.empty())
				{
					//cout << q1.top()+1 << endl;
					printf("%d", q1.top() + 1);
					q1.pop();
				}
				else
				{
					int temp = q0.top();
					q0.pop();
					q1.push(temp);
					//cout << temp + 1 << endl;
					printf("%d", temp + 1);
				}
			}
			else
			{
				if (!q0.empty())
				{
					int temp = q0.top();
					q0.pop();
					q1.push(temp);
					//cout << temp + 1 << endl;
					printf("%d", temp + 1);
				}
				else
				{
					//cout << q1.top() + 1 << endl;
					printf("%d", q1.top() + 1);
					q1.pop();
				}
			}
			printf("\n");
		}


	}
	return 0;
	

}