Team Queue (POJ - 2259 ,队列模拟)
程序员文章站
2022-07-14 12:17:34
...
一.题目链接:
POJ-2259
二.题目大意:
有 t 个小组排队,每个小组有若干人.
当一个人入队时,如果队伍中已有与他同一队伍的人,那么这个人就插到同一队伍人的最后,否则插到队伍最后.
先给出若干入队和出队指令,要求输出出队顺序.
三.分析:
易得:在队伍中,组号相同的人肯定是排在一起的.
也就是说队伍是由组号以及该组的人数确定的.
那不妨,设置 q[0] 为该队伍的组号排列.
对每个小组 i ,再设置一个队列 q[i] 来存储组号为 i 中的元素排列.
每当一个元素 (组号为 i ) 入队时,若 q[i] 为空,说明 q[0] 中无第 i 组成员,那么该元素入 q[i],组号 i 入q[0].
每当一个元素 (组号为 i ) 出队后,若 q[i] 为空,说明 q[0] 中无第 i 组成员,q[0] 弹出队首组号.
四.代码实现:
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long int
using namespace std;
const int M = (int)1e3;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
char s[10];
int team[M * M + 5];
queue <int> q[M + 5];
void init(int t)
{
for(int i = 0; i <= t; ++i)
{
while(!q[i].empty())
q[i].pop();
}
}
int main()
{
int t, num, x, ca = 0;
while(~scanf("%d", &t) && t)
{
printf("Scenario #%d\n", ++ca);
init(t);
for(int i = 1; i <= t; ++i)
{
scanf("%d", &num);
while((num--) > 0)
{
scanf("%d", &x);
team[x] = i;
}
}
scanf("%s", s);
while(s[0] != 'S')
{
if(s[0] == 'E')
{
scanf("%d", &x);
if(q[team[x]].empty())
q[0].push(team[x]);
q[team[x]].push(x);
}
else if(s[0] == 'D')
{
printf("%d\n", q[q[0].front()].front());
q[q[0].front()].pop();
if(q[q[0].front()].empty())
q[0].pop();
}
scanf("%s", s);
}
printf("\n");
}
return 0;
}