切換
舊版
前往
大廳
主題

ZeroJudge - e564: 00540 - Team Queue 解題心得

Not In My Back Yard | 2019-12-15 18:14:25 | 巴幣 0 | 人氣 409

題目連結:


題目大意:
輸入有多筆測試資料。每筆第一列給定一正整數 t (1 ≦ t ≦ 1000),代表有 t 個團體。接著的 t 列輸入,每列開頭給定一正整數 n ,代表該團體有 n 位成員。緊接著 n 個正整數 xi (0 ≦ ㄌxi ≦ 999999 ),代表每位成員的編號。

接著有若干列,每列開頭給定一字串,代表要執行的指令。若字串為「ECQUEUE」,則會給定一正整數 x ,代表要放入佇列的人之編號;若為「DEQUEUE」,則將隊伍最前面的人移出佇列;如果是「STOP」,則代表該測試資料的結尾。

而一個人加入進佇列時,會先看該人所屬的團體是否已經有在佇列裡。如果有,則會排在該團體的最尾端(簡言之為插隊,所以此佇列不是一般資料結構的佇列);反之,排在現在佇列的最尾端。

現在的目標為,對於每個「DEQUEUE」指令,請輸出現在離開隊伍的人的編號(執行指令前,佇列對前端的人之編號)。輸出格式請參見範例輸出。



範例輸入:
2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0


範例輸出:
Scenario #1
101
102
103
201
202
203

Scenario #2
259001
259002
259003
259004
259005
260001


解題思維:
用原本資料結構的佇列即可實現本題的資料結構(以下稱團體佇列)之特性。其中一個佇列,其排隊的單位為團體;而每個團體自己各自有一個佇列,其排隊單位則是人。

每當要把人加入團體佇列時,先看該人所屬團體有無在團體佇列裡(可以用一個布林值表示團體的有無)。如果有就將該人放到所屬團體裡的佇列;沒有的話,就將該人的團體放進團體佇列尾端,並將該人放到團體的佇列裡。

當要從團體佇列移出人時,先看團體佇列最前端的團體是何者。再從該團體的佇列移出該團體最前端的人。如果該團體的佇列已空,則代表該團體的成員都不在團體佇列裡,所以要從團體佇列中移出。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

胖胖貓
題解的連結是上一篇的喔
另外 d718 和這題滿類似的, 不過題目給的號碼會存在不屬於任何一個隊伍時的情況, 其他敘述和要求都是一樣的。
勉強算是這題的加強版吧( ? )
2019-12-16 18:08:40
Not In My Back Yard
感謝糾正以及補充XD
2019-12-16 19:32:49

相關創作

更多創作