[0x12] 132.小组队列

题意

link（more：UVA540）

简化题意：对 \(n\) 个小组排队，每个小组有至多 \(m\) 个成员（每个成员有唯一编号 \(x\)），当一个人来到队伍时，如果队中有同组成员，直接插入其后，否则插入队尾。给定 \(q\) 个入队和出队指令，输出出队顺序。

其中，每个样例有多组用例， \(1\leqslant n,m \leqslant10^3;0\leqslant x<10^6;q\leqslant2\times10^5.\)

思路

首先，易想到需要维护两个队列：

设 \(q0_i\) ：存第 \(i\) 个队内成员的排列；
设 \(q1\) ：存各队伍之间的排列；

∵对于每次输入一个 \(x\) 对其进行入队操作，需要知道它的队伍编号；

∴可以设数组 \(id_i\) 存编号为 \(i\) 的人的队伍编号。

入队操作

易想到对于 \(q1\) 中的每个队伍，我们其实只需要存其队头即可，而后的所有同队成员，可以直接存入本队队列即可，降低思维难度；

∴我们只需维护第一个该队伍进入队列的人即可，换言之，即知道队伍编号的前后顺序足矣。

出队操作

对于 \(q1\) 对头元素，由前文可知，是该队的编号；

∴我们只需每次弹出队头所指队伍的队头元素，若空，则表示 \(q0_i\) 在 \(q1\) 中已空，继而弹出 \(q1\) 的队头元素即可继续下一个队伍。

#include<bits/stdc++.h>

using namespace std;

const int N=1e3+10,M=1e6+10;

int id[M];

queue<int> q0[N],q1;

void init1()

{

	while(!q1.empty()) q1.pop();

	memset(id,0,sizeof(id));

}

void init0(int i)

{ while(!q0[i].empty()) q0[i].pop(); }

int main()

{

	int n,step=1;

	while(cin>>n && n!=0)

	{

		init1();

		printf("Scenario #%d\n",step++);

		for(int i=1;i<=n;i++)

		{

			init0(i);

			int len;

			cin>>len;

			for(int j=1,x;j<=len;j++)

			{

				cin>>x;

				id[x]=i;

			}

		}

		string s;

		while(cin>>s && s!="STOP")

		{

			if(s=="ENQUEUE")

			{

				int add,k;

				cin>>add;

				k=id[add];

				if(q0[k].empty()) q1.push(k);

				q0[k].push(add);

			}

			else

			{

				int out=q1.front();

				printf("%d\n",q0[out].front());

				q0[out].pop();

				if(q0[out].empty()) q1.pop();

			}

		}

		cout<<endl;

	}

	return 0;

}

巴特西

[0x12] 132.小组队列

题意

思路

入队操作

出队操作

最新文章

热门文章