Hdu 1387 Team Queue[队列 || 链表]

1
2
ENQUEUE x 标号为x的人进队
DEQUEUE 队头的人出队

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
<span style="font-size:18px;">
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;

struct Node
{
    int type;
    int num;
    Node *next;
    Node(){
        type = -1;
        num = -1;
        next = NULL;
    }
    Node(int x, int y){
        type = x;
        num = y;
        next = NULL;
    }
} *root, *tail;

const int N = 1e6 + 5;
const int M = 1e3 + 4;
int hash[N];
Node *head[M];

void  insert(int t, int x){
    // 如果删去的是头，那么head不应该是变了吗。。？？ good
    if(head[t] == NULL) {
        tail -> type = t;
        tail -> num = x;
        head[t] = tail;
        tail -> next = new Node();
        tail = tail -> next;
    }
    else {
        Node *p = head[t], *tmp;
        while(p-> next != tail && p -> next -> type == t){
            p = p -> next;
        }// tail may changed..
        if(p -> next == tail){
            tail -> num = x;
            tail -> type = t;
            tail -> next = new Node();
            tail = tail -> next;
        }
        else {
            tmp = p -> next;
            p -> next = new Node(t, x);
            p -> next -> next = tmp;
        }
    }
    return ;
}

//void Print()
//{
//    Node *p = root;
//    while(p -> next != NULL){
//        printf("->%d %d ", p ->type, p -> num);
//        p = p -> next;
//    }
//    printf("n");
//}

//感觉不应该会错，而应该会超时什么的一类。
int main()
{
//    freopen("1.txt", "r", stdin);
    int n, k = 0;
    while(scanf("%d", &n) && n){
        memset(head, NULL, sizeof(head));//remember the first same type.
        memset(hash, 0, sizeof(hash));
        int m, x;
        for(int i = 1; i <= n; i ++){
            scanf("%d", &m);
            for(int j = 1; j <= m; j ++){
                scanf("%d", &x);
                hash[x] = i;
            }
        }
        printf("Scenario #%dn", ++ k);
        root = new Node();// root node is empty;
        tail = new Node();
        root -> next = tail;
        char order[10];
        while(scanf("%s", order) && order[0] != 'S'){
            if(order[0] == 'E'){
                scanf("%d", &x);
                insert(hash[x], x);
            }
            else {
                if(root -> next != tail){// out the queue, may be the queue is empty... nop
                    printf("%dn", root -> next -> num);
                    if(root -> next -> type == root -> next -> next -> type){
                        head[root -> next -> type] = root -> next -> next;
                    }
                    else head[root -> next -> type] = NULL;
                    root = root -> next;
                    root -> type = -1;
                }
            }
        }
        puts("");
        delete root; delete tail;
    }
    return 0;
}
</span>

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
<span style="font-size:18px;">#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
using namespace std;

const int N = 1e6 + 5;
const int M = 1e3 + 5;
int hash[N];
int main()
{
//    freopen("1.txt", "r", stdin);
    int t, k = 1;
    while(scanf("%d", &t) && t){
        memset(hash, 0, sizeof(hash));
        int n, x;
        for(int i = 1; i <= t; i ++){
            scanf("%d", &n);
            for(int j = 1; j <= n; j ++){
                scanf("%d", &x);
                hash[x] = i;
            }
        }
        printf("Scenario #%dn", k ++);
        string ord;
        queue<int> mainp, p[M];
        // 主队里面放队序，副队里面放元素。
        while(cin >> ord && ord != "STOP"){
            if(ord == "ENQUEUE"){
                cin >> x;
                if(p[hash[x]].empty()) mainp.push(hash[x]);
                p[hash[x]].push(x);
            }
            else {
                cout << p[mainp.front()].front() << endl;
                p[mainp.front()].pop();
                if(p[mainp.front()].empty()){
                    mainp.pop();
                }
            }
        }
        cout << endl;
    }
    return 0;
}
</span>