切換
舊版
前往
大廳
主題

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

Not In My Back Yard | 2019-11-30 18:30:04 | 巴幣 2 | 人氣 323

題目連結:


題目大意:
給定一正整數 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」;以上皆非,則看哪個資料結構符合就輸出該資料結構的名稱。

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

創作回應

相關創作

更多創作