AcWing 132. Group queue (queue simulation question)

The question ：

Yes n A group Queue up , There are several people in each group .

When a man comes to the team ,

• If The team already has members of its own team , He just jumped in line behind his team members .
• otherwise , Standing at the back of the line .

Given No more than 2 * 10 ^ 5 Order to join the team （ The number is X People who Come to the team ） and Out of line instructions （ Team leader Out of the team ）, Output The order of leaving the team .

Ideas ：

This problem obviously needs a lot of Small queues , So for the convenience of , Let's go straight ahead N individual queue As Total queue , namely queue<int>[N]

Use one Hashtable ha, Record All entered member numbers Of Group number .

Use one Array st, Record Enter the group to which the member belongs Whether it appears in The total queue in , If by 0 There has never been , Not for 0 Record at the same time The group Appear in the What paragraph Small queues In .

Then the simulation , See code for details .

Be careful ：

• Out of the team When , When The size of a small queue is 0 Be sure to remember to st Array Corresponding place clear 0.

Code ：

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
const int N = 1010;

map<int, int> ha;// The group number corresponding to the member number 
int st[N];// Determine whether members of a group appear in the queue , At the same time, record the group in the sub queue of the group 

int main()
{
    
    int T = 1; 
    int Cnt = 0;
    while (~scanf("%d", &T), T)
    {
    
        queue<int> qq[N];
        memset(st, false, sizeof st);
        ha.clear();

        int h = 1, t = 0;

        while (T--)
        {
    
            int cnt; scanf("%d", &cnt);
            ++t;
            for (int i = 0; i < cnt; ++i)
            {
    
                int tag; scanf("%d", &tag);
                ha[tag] = t;
            }
        }

        char op[20];

        h = 1, t = 0;

        printf("Scenario #%d\n", ++Cnt);
        while (~scanf("%s", op), *op != 'S')
        {
    
            if (*op == 'E')
            {
    
                int x; scanf("%d", &x);
                //cout << "ha[x] " << ha[x] << '\n';
				// When there is no... In the total queue  x  Members of the group to which they belong , Then open a new small queue and press  x
                if (!st[ha[x]])	
                {
    
                    st[ha[x]] = ++t;
                    qq[t].push(x);
                }
                else	// Otherwise, they will be pushed into the small queue of their group 
                {
    
                    qq[st[ha[x]]].push(x);
                }
            }
            else
            {
    
                if (qq[h].size())
                {
    
                    int top = qq[h].front();
                    printf("%d\n", top);
                    qq[h].pop();
                    if (!qq[h].size())
                    {
    
                        st[ha[top]] = 0;
                        h++;
                    }
                }

            }
        }
        puts("");
    }

    return 0;
}