題目大意

給出一個長度為\(M\)序列\(A\)，表示第\(i\)回合將\(A_i\)放入一個箱子中（共有\(M\)回合），再給出一個長度為\(N\)序列\(B\)，表示在\(B_i\)回合執(zhí)行一次\(Get\)操作。\(Get\)操作：\(k++\)，然后輸出箱子中第\(k\)大的元素；\(k\)初始為\(0\)。

分析一下

• 啊箱子就是堆啦
• 假設(shè)正在進(jìn)行第\(B_i\)回合，就是要將\(A_{B_i}\)放進(jìn)箱子中，然后再輸出箱子中第\(i\)小的元素。
• 對于箱子中第\(i\)小的元素，其左邊的元素（第\(i-1\cdots 1\)小）全部比其小，且依次變小，符合大根堆的特性；
• 其右邊的元素（第\(i +1\cdots M\)小）全部比其大，且依次變大，符合小根堆的特性。
• 那么我們可以用一個大根堆與一個小跟堆來維護(hù)箱子里面的元素。將每次要求的答案放在小根堆（當(dāng)然大根堆也可以）的堆頂。
  
• 可以發(fā)現(xiàn)，大根堆中的元素個數(shù)始終為\(i-1\)。

操作流程

• 首先外循環(huán)枚舉\(B\)序列。將\(A\)序列中的元素塞進(jìn)大根堆中。
• 維護(hù)大根堆中的元素只能有\(i-1\)個，即每當(dāng)個數(shù)超出時，將大根堆的堆頂移至小根堆中。
• 輸出小根堆的堆頂（即答案）。因為這個答案已經(jīng)貢獻(xiàn)完了，所以再將其塞回至大根堆中。

轉(zhuǎn)載于:https://www.cnblogs.com/JackHomes/p/9322849.html

總結(jié)

以上是生活随笔為你收集整理的题解【黑匣子_NOI导刊2010提高（06）】(洛谷P1801)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。