欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}