題目網址: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 個由空白隔開整數 x1 x2 … xM,即為 ADD 每次要放入的數字,ADD 操作會依照 input 的順序放入。而第二行有 N 個整數 p1 p2 … pN,表示 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

Source code on gist.