题目描述
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;
}
0605)
