UVa 540 Team Queue

UVa 540 Team Queue

Team Queue

Time Limit: Unknown Memory Limit: Unknown
Total Submission(s): Unknown Accepted Submission(s): Unknown



https://uva.onlinejudge.org/i…


Accepted Code

Notes

題意:
團隊排隊,每次 ENQUEUE 先檢查隊伍裡有沒有自己人,若有,則插到自己人的最後,否則排到隊尾。出隊 DEQUEUE 按正常規則來。

思路:
1.用一個陣列 queue 來存佇列,佇列中每個元素包含三個資訊:團隊編號、團隊頭指標、團隊尾指標。並用 qh 標誌隊首,用 qt 標誌隊尾。
2.每次 ENQUEUE 先檢查 queue 中有沒有自己所屬團隊,若有,插到團隊的最後。若沒有,則在 queue 的最後新建一個團隊,並插入這個人,然後把隊尾標誌後移。
3.每次 DEQUEUE 就把 queue 隊首的團隊中的第一個人輸出,如果該團隊空了,就把隊首標誌後移。

感受:
這題如果只用一個佇列來做(佇列中的元素包含兩個資訊:某人的編號、他所屬團隊),就需要便歷整個隊伍來查詢自己所屬團隊,時間開銷太大,過不了。
然後改進一下得到如上程式碼,用 queue 存團隊編號以及該團隊的頭、尾指標,這樣一來主佇列大幅縮短,遍歷的時間開銷就大幅降低了。

附: