P2776 [SDOI2007]小組隊列

題目背景

嘛，這道非常簡單的給大家提供信心的省選題洛谷居然沒有！

這麼簡單的題怎麼可以沒有！

給大家提升士氣是義不容辭的責任！

所以我就來補一下啦..

值得一提的是，標程是我自己做的..

很渣，因為數據很水所以能AC..

大神勿噴..

題目描述

有 m 個小組， n 個元素，每個元素屬於且僅屬於一個小組。

支持以下操作：

push x：使元素 x 進隊，如果前邊有 x 所屬小組的元素，x 會排到自己小組最後一個元素的下一個位置，否則 x 排到整個隊列最後的位置。

pop：出隊，彈出隊頭並輸出出隊元素，出隊的方式和普通隊列相同，即排在前邊的元素先出隊。

輸入輸出格式

輸入格式：

第一行有兩個正整數 n, m，分別表示元素個數和小組個數，元素和小組均從 0 開始編號。

接下來一行 n 個非負整數 Ai，表示元素 i 所在的小組。

接下來一行一個正整數 T ，表示操作數。

接下來 T 行，每行為一個操作。

輸出格式：

對於每個出隊操作輸出一行，為出隊的元素。

輸入輸出樣例

4 2
0 0 1 1
6
push 2
push 0
push 3
pop
pop
pop

2
3
0

說明

對於30%的數據，1≤n≤100,1≤m≤10,T≤50。

對於100%的數據，1≤n≤100000,1≤m≤300,T≤100000,輸入保證操作合法。

第一次用到二維隊列

用last來表示每一個小組內元素出現的順序

q隊列表示每一個小組出現的順序

我們想一下，如果一個元素所屬的小組在之前出現過

那麼我們直接加到last隊列里就好

這樣可以保證按照小組的順序輸出

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 int read(int & n)
 8 {
 9     char c='.';int x=0,flag=0;
10     while(c<'0'||c>'9')
11     {
12         c=getchar();
13         if(c=='-')flag=1;
14     }
15     while(c>='0'&&c<='9')
16     {
17         x=x*10+(c-48);
18         c=getchar();
19     }
20     if(flag==1)n=-x;
21     else n=x;
22 }
23 const int MAXN=10000001;
24 queue<int>q,last[301];
25 int group[MAXN];
26 int main()
27 {
28     int n,m,p,meiyong;
29     read(n);read(meiyong);
30     for(int i=0;i<n;i++)
31         read(group[i]);
32     read(m);
33     for(int i=1;i<=m;i++)
34     {
35         string s;
36         cin>>s;
37         if(s=="push")
38         {
39             read(p);
40             if(last[group[p]].empty())
41             q.push(group[p]);
42                 last[group[p]].push(p);
43         }
44         else
45         {
46             printf("%d\n",last[q.front()].front());
47             last[q.front()].pop();
48             if(last[q.front()].empty())
49             q.pop();
50             
51         }
52     }
53     return 0;
54 }