ACM/ICPC 之 "嵌套"队列 -插队(POJ2259)

86 阅读 0 评论 57 点赞

我是靠谱客的博主自由帽子，最近开发中收集的这篇文章主要介绍ACM/ICPC 之 "嵌套"队列 -插队(POJ2259)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

　　这里插队的意思就是排队时遇到熟人则插到其后，否则排到队尾。（这个习惯不太好）（题意）

　　题目要求我们模拟“插队模型”和队列的入队和出队完成此算法。

　　由于题目的输入输出很多，此题的查找操作（找到熟人）需要控制到O(1)，因此映射每一个人际圈（所属同一队伍的意思）的编号而非每个人就很重要了，可以将不同人际圈的编号依次入队，而非每个人依次入队，这样主队列中的元素就是各人际圈的编号，而将入队的每个人压入到该人际圈，这样一种思想就是标题上所写的"嵌套"队列了（纯属杜撰）。

　　具体代码如下：

 1 //嵌套队列-插队：遇到熟人则插在其后，否则在队尾，按操作输入后输出Dequeue的编号
 2 //Time:141ms    Memory:760K
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<queue>
 7 using namespace std;
 8 #define MAX 1001
 9 #define MAX_NUM 1000001 //编号
10 queue<int> team[MAX];    //队伍
11 queue<int> q;     //主队列-保存各队伍入队顺序
12 bool v_team[MAX];    //队列已入队标记
13 int ele[MAX_NUM];    //映射：编号-队伍
14 int main()
15 {
16     int n;    //队列数
17     int scenario = 0;
18     
19     while (scanf("%d", &n), n)
20     {
21         /*Init*/
22         memset(v_team, false, sizeof(v_team));
23         for (int i = 0; i < n; i++)
24             while (!team[i].empty()) team[i].pop();
25         while (!q.empty()) q.pop();
26         /*Input*/
27         for (int i = 0; i < n; i++)
28         {
29             int m;    //队员数
30             scanf("%d", &m);
31             for (int j = 0; j < m; j++)
32             {
33                 int mem;
34                 scanf("%d", &mem);
35                 ele[mem] = i;
36             }
37         }
38         /*Main*/
39         char command[10];
40         printf("Scenario #%dn", ++scenario);
41         while (scanf("%s", command), strcmp(command, "STOP"))
42         {
43             if (!strcmp(command, "ENQUEUE"))    //ENQUEUE
44             {
45                 int mem;
46                 scanf("%d", &mem);
47                 //不存在存在该元素队列
48                 if (!v_team[ele[mem]])
49                 {
50                     v_team[ele[mem]] = true;
51                     q.push(ele[mem]);    //压入team number
52                 }
53                 team[ele[mem]].push(mem);
54             }
55             else {    //DEQUEUE
56                 int mem = team[q.front()].front();
57                 team[q.front()].pop();
58                 if (team[ele[mem]].empty())
59                 {
60                     v_team[ele[mem]] = false;
61                     q.pop();    //抛出team number
62                 }
63                 printf("%dn", mem);
64             }
65         }
66         printf("n");
67         
68     }
69     
70     return 0;
71 }