问题描述

t 个团队在餐厅前准备排队。 他们的排队规则是:
初始队伍为空。一个人要排进队伍前, 先搜索队伍中是否有他的队友。 如果
有, 这名成员就直接站在最后一个队友的后面,如果没有,那么这名成员只能排
在整个队伍的最后面。排队中途,队首的人可能被要求离开队伍。
依照上述排队规则,给出一些操作,操作有以下两种:
(1) IN x , – 编号为 x 的成员进入队伍;
(2) OUT , – 队首成员离开队伍。
操作结束后按顺序输出所有离开成员的编号。

★数据输入
输入第一行为一个正整数 t,代表团队的数量(1<=t<=1000)。
接下来 t 行,每行第一个整数为该团队的人数 n(1<=n<=1000), 接着 n 个整
数代表 n 个成员的编号 id, id 唯一且 1<=id<=1000000。
接下来 q 行操作(1<=q<=200000),注意可能出现已经在队列中的人重复入队
的情况,忽略这样的操作。

★数据输出
输出第一行为整数 m,离开队伍的成员的数量。
接下来 m 行按序输出离开的成员的 id。

输入示例 输出示例
2
3 101 102 105
3 103 104 106
12
IN 101
IN 103
IN 104
IN 102
IN 105
IN 106
OUT
OUT
OUT
OUT
OUT
OUT
6
101
102
105
103
104
106
输入示例 输出示例
2
5 2501 2502 2503 2504 2505
6 26001 26002 26003 26004 26005 26006
14
IN 2501
IN 26001
IN 2502
IN 2503
IN 2504
IN 2505
OUT
OUT
IN 2602
IN 2603
OUT
OUT
OUT
OUT
6
2501
2502
2503
2504
2505
26001

思路

  定义一个存team的队列qq,其中,每个元素team是一个队列。也就是说,定义一个存队列的队列。

  但是由于qq要支持随机访问,故用数组模拟队列。qq中的每个元素team用std::queue或者数组模拟都可以。

  由于操作数较多(1<=q<=200000) ,若每次操作依据id查找所属team,再查找team再queue中的位置会消耗较多时间,

  所以用数组teamid存对应id所属的team编号(从1开始),用数组teamindex存对应team在qq中的index

  有新人入队时,先检测他所属的team,若在qq中找到,则push在team末尾;若找不到,则在qq中新加一个team,把这个id加入这个team

  出队时,对qq中的第1个team实行pop操作,再判断该team是否为空,若为空,对qq pop该team

 

code

 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
#include <queue> #define MAXID 1000003
#define MAXTEAM 1003
#define MAXOP 200003 int teamid[MAXID] = {};//teamid[id]
bool inque[MAXID] = {}; //inque[id]
int teamindex[MAXTEAM] = {};//teamindex[teamid[id]] queue<int> ans;
queue<int> qq[MAXOP]; int main()
{
int i,j,u;
int t,id,op;
char str[]={};
scanf("%d",&t);
for(i=;i<=t;i++)
{
scanf("%d",&u);
for(j=;j<=u;j++)
{
scanf("%d",&id);
teamid[id] = i;
}
} int l=,r=;
scanf("%d",&op);
getchar();
for(i=;i<=op;i++)
{
scanf("%s",str);
if(strcmp(str,"IN")==)
{
scanf("%d",&id);
getchar();
if(inque[id]==false)
{
inque[id] = true;
if(teamindex[teamid[id]]==)
{
++r;
qq[r].push(id);
teamindex[teamid[id]] = r;
}
else
{
qq[teamindex[teamid[id]]].push(id);
}
}
}
else if(strcmp(str,"OUT")==)
{
if(l<=r)
{
inque[qq[l].front()] = false;
ans.push(qq[l].front());
int tmp = qq[l].front();
qq[l].pop();
if(qq[l].empty())
{
teamindex[teamid[tmp]] = ;
++l;
}
}
}
} printf("%d\n",ans.size());
while(!ans.empty())
{
printf("%d\n",ans.front());
ans.pop();
} return ;
}

之前贴的代码有bug (新代码已修正):

  (1)在OUT操作时应判断 (l<=r);

  (2)qq数组定义过小,重新定义为 queue<int> qq[MAXOP];,其中 MAXOP = 200003

    注意,qq数组最好在全局定义,不然OJ上会SO

05-24 04:06