2011-05-01-3-uva-501-black-box.md

layout	title	date	tags
post	[UVa] 501 - Black Box	2011-05-01	UVa heap | 堆積 priority queue | 優先佇列

題目網址：501 – Black Box

題目概述

有一個盒子，這盒子裡有個特別的整數 n（題目是以 i 作為符號，但我不喜歡用 i）。現在可以對這個盒子做以下兩種操作：

• ADD(x)：將 x 這個整數放到盒子內
• GET：將 n 加 1，並找出盒子內第 n 小的整數

題目會給予 ADD 的操作次數 M 與 GET 的操作次數 N。

題目的輸入為 ADD 操作時所丟進盒子裡的數字 x，以及執行 GET 操作時盒子類有多少數字。要求的輸出為，每次 GET 所得到的數字。

Technique Detail

• |x| < 2,000,000,000
• M ≤ 30,000
• N ≤ M

輸入格式

測試資料開頭會有一個整數 K，表示接下來會有 K 筆測試資料，在 K 之後會有一空白行，並且接下來的個筆測試資料間皆由一個空行隔開。

每筆測試資料開頭有兩個整數 M N，如同題目敘述所說，M 為 ADD 的操作次數，N 為 GET 的操作次數。接下來有兩行，第一行有 M 個由空白隔開整數 x₁ x₂ … x_M，即為 ADD 每次要放入的數字，ADD 操作會依照 input 的順序放入。而第二行有 N 個整數 p₁ p₂ … p_N，表示 GET 操作發生的時機，該時機即為當盒子內的數字為 p 時，就會執行 GET 操作。

輸出格式

對於每筆測試資料，輸出 N 個整數，也就是輸出每次 GET 所得到的數值。這些數字可以用空格或是換行分隔，不限定。但要注意，每筆測試資料的輸出，都需要以換行做分隔。

---

解題思路

最初的第一個想法為 binary search tree，於是很愚蠢的使用了 STL 中的 set 來慢慢搜尋。想說每次 ADD 就把數字丟進 set 中。再用 iterator 來取得 GET 所要的值，以為只要 *( set.begin() + p ) 就可以拿到 GET 的值了。結果出現 compilation error，才想起來 set 的 iterator 沒有 random access 的特性。

於是開始思考自己實現 binary search tree，但一般的 BST 如果出現不平衡的狀況，會造成時間複雜度飆升。想到最近作業寫了 AVL tree，但我的 AVL tree 是用動態配置記憶體的方式寫的，應該是沒寫好造成瘋狂的 RE，所以決定先放棄這方法了。

突然看到 priority queue，想到 GET 的順序都是遞增的。所以使用兩個 priority queue，一個用作 max-heap（頂端元素為該 heap 中最大值），另一個用作 min-heap（頂端元素為該 heap 中最小值）。只要保持 max-heap 一直擁有 n - 1 的數字就好，這樣 min-heap 的頂端就是 GET 所要的值。

min-heap 與 max-heap 也需要是有序的狀態，數字不能隨便放。min-heap 的內的所有數字都需要大於 max-heap 中的所有數字，由於 heap 的性質，可以得知兩丁端元素必為排序後相鄰的數字。

在進行 ADD 操作時，要依照 min-heap 與 max-heap 的頂端元素來決定要將數字加入哪一邊。若 x 大於 max-heap 的頂端元素，就將 x 丟入 min-heap。若 x 小於等於 max-heap 的頂端元素，就將 x 丟入 max-heap。如此一來，才能維持兩個 heap 之間的有序性。若任意放入 heap 可能會導致 min-heap 的頂端元素小於 max-heap 的頂端元素的狀況。

在邊進行 ADD 操作時，也一邊檢查盒子內的數字數量是否達到觸發 GET 操作的時機。每當觸發 GET 操作，就讓 max-heap 的元素數量等於 n - 1 個。如此一來，min-heap 的頂端元素就是第 n 小的數字了。

Source Code

<script src="https://gist.github.com/KuoE0/1605015.js"></script>

Source code on gist.