洛谷P2776 [SDOI2007]小组队列题解

题目传送门

对于新手难度适宜的一个数据结构题

题面简述

将一个队列分为若干个组，组内的成员入队时直接插入到小组后面，队内无小组成员时插入到队尾。

有两种操作：(push) 和 (pop)（具体操作和队列一样，是针对大队列的）

思路

模拟

代码思路简述

用大数组存储每个元素的组别。

用若干个小队列和一个大队列来模拟：

大队列存放小组的排名，小组没人就弹出队首小组；

每个小队列放组员顺序，在压入组员时，直接压入在对应小组的队列后面，弹出直接弹出队首组员。

代码

#include<iostream>
#include<queue>
using namespace std;
queue<int> q[305];//各个小组
int b[100005];//组员所在的组
queue<int> all;//大队
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>b[i];
    int t;
    cin>>t;
    while(t--)
    {
        string temp;
        cin>>temp;
        if(temp=="pop")
        {
            cout<<q[all.front()].front()<<endl;//输出小组的队首
            q[all.front()].pop();//弹出小组队首
			if(q[all.front()].empty())
                all.pop();//小组没人了就在大队中将小组弹出
        }
        else
        {
            int x;
            cin>>x;
            if(q[b[x]].empty())
                all.push(b[x]);//如果大队中没有所在小组就连同小组排在队尾
            q[b[x]].push(x);//在小组中压入组员
        }
    }
    return 0;
}

完结撒花 (。・∀・)ノ花花花