PQJ2259 - 团队队列

题设

【问题描述】

在团队队列中每个成员都属于一个团队，如果一个成员进入队列，它首先从头到尾搜索队列，以检查它的一些队友（同一队的成员）是否已经在队列中，如果是，它会进入到该团队的后面，如果不是，它会从尾部进入队列并成为新的最后一个成员。成员出队是按常规队列操作，按照出现在队列中的顺序从头到尾进行处理。你的任务是编写一个模拟这样的团队队列的程序。

【输入形式】

每个测试用例都以团队个数t开始（1≤t≤1000），然后是团队描述，每个描述包含属于团队的成员个数和成员编号列表，成员编号为0到999999之间的整数，一个团队最多可以包含1000个成员。然后是一系列命令，有三种不同的命令：

① ENQUEUE p：成员p进入队列。

② DEQUEUE：队列中第一个成员出来并将其从队列中删除。

③ STOP：当前测试用例结束。

【输出形式】

​ 对于每个DEQUEUE命令，以单独一行输出出队的成员。

【样例输入】

2

3 101 102 103

3 201 202 203

ENQUEUE 101

ENQUEUE 201

ENQUEUE 102

ENQUEUE 202

ENQUEUE 103

ENQUEUE 203

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

STOP

【样例输出】

101

102

103

201

202

203

题解

本题作者之前做过一遍，当时用的是STL模版库中的deque，于是这次便想绕过STL，直接用数组进行模拟。为此准备了6个数组，其中inqueue用于记录某一团队是否位于队列中；queue用于记录团队顺序；group是一个二维数组用于记录在团队中的成员；member则为成员对应的团队；st和ed用于记录各团队成员的首和尾。这其实就是实现deque的功能：头尾均可插入和删除。

#include <cstdio>
#include <cstring>
const int maxn1 = 1000 + 5;
const int maxn2 = 10000000 + 10;

int inqueue[maxn1];
int queue[maxn1];
int group[maxn1][maxn1];
int member[maxn2];
int st[maxn1], ed[maxn1];
int head, tail;
int n;
char s[10];

bool solve() {
  scanf("%s", s);
  switch (s[0]) {
    case 'S':
      return false;
    case 'E':
      int k;
      scanf("%d", &k);
      if (inqueue[member[k]]) {
        group[member[k]][++ed[member[k]]] = k;
      } else {
        queue[tail] = member[k];
        tail++;
        if (tail == maxn1) tail = 0;
        inqueue[member[k]] = 1;
        st[member[k]] = ed[member[k]] = 1;
        group[member[k]][1] = k;
      }
      break;
    case 'D':
      int fr = queue[head];
      printf("%d", group[fr][st[fr]++]);
      if (st[fr] > ed[fr]) {
        inqueue[fr] = 0;
        head++;
        if (head == maxn2) head = 0;
      }
      printf("\n");
      break;
  }
  return true;
}

int main() {
  // freopen("in.txt", "r", stdin);
  head = 0, tail = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int k, m;
    scanf("%d", &k);
    while (k--) {
      scanf("%d", &m);
      member[m] = i;
    }
  }
  while (solve()) {
  }
}