Problem Solving►UVa

UVa 540 - Team Queue

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

三種操作:

  • ENQUEUE x : 若 x 所屬的團隊成員已有在內的，就排進團隊內的最後一個。若沒有，則排進隊伍的最後一個。
  • DEQUEUE : 將隊伍最前面的元素移除，並輸出此元素。
  • STOP : 結束。

Solution

直接用兩個 queue 去模擬排隊的情形。

一個 queue 用來記錄團隊的順序，另一個用來存團隊內元素的順序。

Code

UVa 540
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<cstdio>
#include<queue>
using namespace std;

int main()
{
    static int ele[1000000];//元素在哪個團隊
    int T, Case = 1;
    int in[1001] = {};//此團隊有幾個人已經排進去了
    queue<int> teamQ, eleQ[1001];//存團隊的順序,團隊中元素的順序

    while (scanf("%d", &T) && T)
    {
        int i, n, temp;
        for (i = 1; i <= T; i++)
        {
            scanf("%d", &temp);
            for (int j = 0; j < temp; j++)
            {
                scanf("%d", &n);
                ele[n] = i;
            }
        }

        char str[10];
        printf("Scenario #%d\n", Case++);
        while (scanf("%s", &str) && str[0] != 'S')
        {
            int team;
            if (str[0] == 'E')
            {
                scanf("%d", &n);
                team = ele[n];
                if (!in[team])//這個團隊中第一個進去排隊的
                    teamQ.push(team);//將團隊排進去
                eleQ[team].push(n);//排入團隊中
                in[team]++;
            }
            else
            {
                team = teamQ.front();
                printf("%d\n", eleQ[team].front());
                eleQ[team].pop();
                in[team]--;
                if (!in[team])//此團隊已沒人在排
                    teamQ.pop();
            }
        }

        putchar('\n');
        
        //init
        for (i = 0; i <= T; i++)
            in[i] = 0;
        for (i = 0; i <= T; i++)
            while (!eleQ[i].empty())
                eleQ[i].pop();
        while (!teamQ.empty())
            teamQ.pop();
    }

    return 0;
}