這道題目、主要是對(duì)隊(duì)列的靈活應(yīng)用。其實(shí)就是一道模擬題目，只要你洞察出題目的本質(zhì)就十分簡(jiǎn)單。題目意思大體是有多組測(cè)試數(shù)據(jù)，每組的一開始是一個(gè)數(shù)字t，代表一共有多少的團(tuán)隊(duì)，接著是t行輸入，每一行都由一個(gè)數(shù)字n開頭，表示隊(duì)伍的人數(shù)。在這之后，輸入諾干行的操作指令，E x代表入編號(hào)為x的入隊(duì)列，這里的隊(duì)列是一個(gè)新的而且只有一個(gè)的新隊(duì)列。D代表就是出隊(duì)列、同時(shí)輸出該元素、S表示停止模擬。
題目的具體要求是，每次入隊(duì)里前，先從隊(duì)列頭掃描到隊(duì)列尾，如果隊(duì)列里有隊(duì)友，就排在隊(duì)友們的最后面(不是該隊(duì)友的后面，是整隊(duì)隊(duì)友的最后面)。如果沒有隊(duì)友則，直接排在隊(duì)列的最后面。出隊(duì)列的沒什么特別的了。
Keys:其實(shí)我們可以通過(guò)簡(jiǎn)單的模擬、發(fā)現(xiàn)。由第一個(gè)隊(duì)員到最后一個(gè)隊(duì)員入隊(duì)列，或者中間有其他出隊(duì)列。該隊(duì)列始終可以看成是兩個(gè)隊(duì)列的隊(duì)列。又因?yàn)轭}目要求常數(shù)的時(shí)間、
所以我們不可能把時(shí)間浪費(fèi)在某個(gè)隊(duì)員屬于哪一個(gè)隊(duì)里，所以可以用映射、也就是map來(lái)解決這個(gè)問(wèn)題。map<int, int>這個(gè)結(jié)構(gòu)剛好能映射這種關(guān)系。接下去就是要有一個(gè)q2[maxn]來(lái)表示所有初始化的隊(duì)列。一個(gè)q來(lái)表示新隊(duì)列，這個(gè)q其實(shí)就是隊(duì)列的隊(duì)列。
1 #include <queue>
2 #include <string>
3 #include <map>
4 #include <iostream>
5 using namespace std;
6
7 const int maxn = 1024;
8
9
10 int main() {
11
12 int t, n, k = 0;
13 while (cin >> t, t) {
14 // 列隊(duì)編號(hào)
15 cout << "Scenario #" << ++k << endl;
16 int qid = 1;
17 map<int, int> team;
18 while (t--) {
19 cin >> n;
20 for (int i = 0; i < n; i++) {
21 int uid;
22 cin >> uid;
23 team[uid] = qid;
24
25 }
26 qid++;
27 }
28
29 // uid是隊(duì)員編號(hào)、 tid是那一對(duì)隊(duì)的編號(hào)
30 queue<int> q,q2[maxn];
31 string op;
32 int uid;
33
34 while (cin >> op, op[0] != 'S') {
35
36 // 入隊(duì)列
37 if ('E' == op[0]) {
38 cin >> uid;
39 int tid = team[uid];
40 if (q2[tid].empty()) q.push(tid);
41 q2[tid].push(uid);
42
43 }
44 // 出隊(duì)列
45 if ('D' == op[0]) {
46
47 int tid = q.front();
48 int x = q2[tid].front();
49 q2[tid].pop();
50 cout << x << endl;
51 if (q2[tid].empty()) q.pop();
52
53 }
54
55 }
56
57 cout << endl;
58
59
60 }
61
62 }