ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - e548: 11995 - I Can Guess the Data Structure!　解題心得

Not In My Back Yard | 2019-11-30 18:30:04 | 巴幣 2 | 人氣 486
題目連結：
題目大意：
給定一正整數 n （1 ≦ n ≦ 1000），代表接著有 n 列的指令。每列的第一個正整數（只會是 1 或是 2），代表指令的種類。而後還會給定第二個正整數 x （0 ＜ x ≦ 100）。

如果指令的種類為 1 ，代表要從神奇袋子中放入整數 x ；如果是種類 2 ，則代表要從神奇袋子中拿出其中的一個元素，而已知該元素值為 x。

而神奇袋子可能為堆疊（Stack）、佇列（Queue）、優先佇列（Priority Queue）這三種資料結構中的一種。請從給定的指令以及其結果，推出神奇袋子應為哪種資料結構。

如果是堆疊，請輸出「stack」；是佇列，輸出「queue」；是優先佇列，則輸出「priority queue」；倘若無法確定，輸出「not sure」；如果途中出現不可能的操作，請輸出「imposibble」。

範例輸入：
6
1 1
1 2
1 3
2 1
2 2
2 3
6
1 1
1 2
1 3
2 3
2 2
2 1
2
1 1
2 2
4
1 2
1 1
2 1
2 2
7
1 2
1 5
1 1
1 3
2 5
1 4
2 4
範例輸出：
queue
not sure
impossible
stack
priority queue
解題思維：
這題就直接宣告（或是自己實作也是可以的）堆疊、佇列、優先佇列各一個。然後按照給定的指令做事。

碰到指令種類 1 就放入 x ；碰到種類 2 就從中移出元素，並與 x 比對。

如果有資料結構在途中沒有出錯過（從空的結構裡移出元素）或是沒有任何一次移出的元素與給定的 x 不符合。則神奇袋子有可能是該資料結構。

如果所有資料結構都有出錯過或是不符合 x ，則輸出「impossible」；如果神奇袋子可以是兩種（含）以上的資料結構，輸出「not sure」；以上皆非，則看哪個資料結構符合就輸出該資料結構的名稱。

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

創作回應

相關創作

更多創作