b034. Arvin 拉麵店 - TCFSH CIRC Judge

內容

本題出自 YTP 2019 初賽 p. 6

在這個 AI 盛行的世代，這個世界已經沒剩下多少工作還沒被人工智慧或者是機器人取代，即便連 AI 之父──Arvin 也因為被自己創造出來的 AI 取代而失去了工作。年過 20 的他只好前進拉麵圈──由於種類繁多而至今仍無法被 AI 完全掌控的事業，並且試圖在拉麵圈闖出一番事業。
然而成功創業並不是像炸雞排那麼簡單，身為拉麵店唯一一位員工，Arvin 需要妥善利用他的時間，畢竟從備料、煮麵、擺盤到照顧店裡的財神貓都是他的工作，他將每份工作給予一個優先值 $ p $ ，並且試圖藉此最佳化他的時間分配。Arvin 有以下習慣：

Arvin 只會挑優先度最高的或者最低的其中一個做，因為要決定中間的那些工作的順序對他這個選擇障礙者實在是太麻煩了。
Arvin 在想要做優先度高的工作的時候，會唸一串很神奇的咒語，唸起來恰巧跟英文的「Pop Large」很像，所以在遇到 Arvin 說一句類似「Pop Large」的時候，就代表他想要做優先度最高的工作。
同理，Arvin 在想要做優先度低的工作的時候，就會唸一段和「Pop Small」很像的咒語，我們也可以藉此判斷他想要做優先度最低的工作。
打烊時，無論此時工作有沒有做完，他就會不顧一切大喊和「End」十分相似的咒語，鼓勵他一天以來的辛勞，然後就下班了。

請問你能幫他完成寫一個程式幫助他好好利用時間，賺到最多的錢嗎？

輸入說明

有一連串的指令輸入，一個指令一行。

INSERT p：增加一份優先值為 $ p $ 的工作。
POP_LARGE：請幫 Arvin 找出目前優先值最大的工作、印出該優先值並將該份工作從工作堆移除。如果當時沒有工作，請輸出「Nothing To Do :)」。
POP_SMALL：請幫 Arvin 找出目前優先值最小的工作、印出該優先值並將該份工作從工作堆移除。如果當時沒有工作，請輸出「Nothing To Do :)」。
END：代表測試資料的結束。

$ 0 \leq p \leq 10^9 $ ，最多有 $ 1000000 $ 個指令，相同的優先值 $ p $ 可能出現不只一次。

輸出說明

如果遇到指令是 POP_LARGE 或 POP_SMALL，請輸出一行，包含一個整數，代表該指令所要印出的優先值。

範例輸入 #1

// 1
POP_LARGE
INSERT 79
INSERT 53
INSERT 3
POP_SMALL
INSERT 85
POP_SMALL
INSERT 85
INSERT 35
END
// 2
POP_LARGE
INSERT 11
INSERT 38
POP_SMALL
INSERT 12
INSERT 73
INSERT 18
POP_SMALL
INSERT 39
INSERT 22
INSERT 53
POP_LARGE
INSERT 8
POP_LARGE
INSERT 91
POP_LARGE
POP_SMALL
INSERT 46
INSERT 81
END

範例輸出 #1

// 1
Nothing To Do :)
3
53







// 2
Nothing To Do :)
11
12
73
53
91
8

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <50M

提示：

類似題：GreenJudge e025: 1.雲端列印

標籤:

multiset pbds tree

出處:

YTP 2019 Pre [管理者：

nevikw39 ($\mathscr{nevikw}\pmb{39}\in\mathbf{37}^{th}$)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」