題目描述
Black Box 是一種原始的數據庫。它可以儲存一個整數數組，還有一個特別的變量?i。最開始的時候 Black Box 是空的．而?i=0。這個 Black Box 要處理一串命令。
命令只有兩種：
-
ADD(x)：把?x?元素放進 Black Box; -
GET：i?加?1，然后輸出 Black Box 中第?i?小的數。
記住：第?i?小的數，就是 Black Box 里的數的按從小到大的順序排序后的第?i?個元素。
我們來演示一下一個有11個命令的命令串。（如下表所示）
| 序號 | 操作 | i | 數據庫 | 輸出 |
|---|---|---|---|---|
| 1 | ADD(3) | 0 | 3 | / |
| 2 | GET | 1 | 3 | 3 |
| 3 | ADD(1) | 1 | 1,3 | / |
| 4 | GET | 2 | 1,3 | 3 |
| 5 | ADD(-4) | 2 | ?4,1,3 | / |
| 6 | ADD(2) | 2 | ?4,1,2,3 | / |
| 7 | ADD(8) | 2 | ?4,1,2,3,8 | / |
| 8 | ADD(-1000) | 2 | ?1000,?4,1,2,3,8 | / |
| 9 | GET | 3 | ?1000,?4,1,2,3,8 | 1 |
| 10 | GET | 4 | ?1000,?4,1,2,3,8 | 2 |
| 11 | ADD(2) | 4 | ?1000,?4,1,2,2,3,8 | / |
現在要求找出對于給定的命令串的最好的處理方法。ADD?命令共有?m?個，GET?命令共有?n?個。現在用兩個整數數組來表示命令串：
-
a1?,a2?,?,am?：一串將要被放進 Black Box 的元素。例如上面的例子中?a=[3,1,?4,2,8,?1000,2]。
-
u1?,u2?,?,un?：表示第?ui??個元素被放進了 Black Box 里后就出現一個?
GET?命令。例如上面的例子中?u=[1,2,6,6]?。輸入數據不用判錯。
輸入格式
第一行兩個整數?m?和?n，表示元素的個數和?GET?命令的個數。
第二行共?m?個整數，從左至右第?i?個整數為?ai?，用空格隔開。
第三行共?n?個整數，從左至右第?i?個整數為?ui?，用空格隔開。
輸出格式
輸出 Black Box 根據命令串所得出的輸出串，一個數字一行。
輸入輸出樣例
輸入 #1復制
7 4 3 1 -4 2 8 -1000 2 1 2 6 6
輸出 #1復制
3 3 1 2
說明/提示
數據規模與約定
- 對于?30%?的數據，1≤n,m≤104。
- 對于?50%?的數據，1≤n,m≤105。
- 對于?100%?的數據，1≤n,m≤2×105,∣ai?∣≤2×109，保證?u?序列單調不降。
代碼實現：
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
? ? int m, n;
? ? cin >> m >> n;
? ? vector<int> a(m);
? ? for (int i = 0; i < m; ++i) {
? ? ? ? cin >> a[i];
? ? }
? ? vector<int> u(n);
? ? for (int i = 0; i < n; ++i) {
? ? ? ? cin >> u[i];
? ? }
? ??
? ? priority_queue<int> maxHeap;
? ? priority_queue<int, vector<int>, greater<int> > minHeap;
? ??
? ? int ptr = 0; ?// 當前處理到a的位置
? ? int getCount = 0; ?// 當前GET命令的數量
? ??
? ? for (int i = 0; i < n; ++i) {
? ? ? ? int target = u[i];
? ? ? ? // 處理ADD操作直到ptr達到target
? ? ? ? while (ptr < target) {
? ? ? ? ? ? int num = a[ptr++];
? ? ? ? ? ? maxHeap.push(num);
? ? ? ? ? ? // 調整兩個堆的平衡
? ? ? ? ? ? if (maxHeap.size() > getCount + 1) {
? ? ? ? ? ? ? ? minHeap.push(maxHeap.top());
? ? ? ? ? ? ? ? maxHeap.pop();
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? // 處理GET操作
? ? ? ? ++getCount;
? ? ? ? cout << maxHeap.top() << endl;
? ? ? ? // 調整兩個堆的平衡
? ? ? ? if (!minHeap.empty()) {
? ? ? ? ? ? maxHeap.push(minHeap.top());
? ? ? ? ? ? minHeap.pop();
? ? ? ? }
? ? }
? ??
? ? return 0;
}
