题目描述
黑盒子代表一个原始的数据库。
它可以用来储存整数数组,并且它拥有一个特殊变量i。
在最开始,黑盒子是空的,并且i=0。
现在对黑盒子进行一系列的操作处理,操作包括以下两种:
1、ADD(x):表示将x加入到黑盒子中。
2、GET:使i增加1,输出黑盒子中第i小的数值(即将所有数按升序排序后的第i个数)。
下面给出一个具体例子:
序号 | 操作 | 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 |
为了方便描述,下面我们定义两个序列:
1、A(1),A(2),…,A(M):这个序列由加入到黑盒子内的所有元素按加入顺序排列后得到,上例中的A序列为(3,1,-4,2,8,-1000,2)。
2、u(1),u(2),…,u(N): 这个序列的第i项表示的是第i次GET操作时,盒子内元素的数量。上例中的u序列为(1,2,6,6)。
现在请你根据给出的序列A和u求出操作过程中输出的所有数值。
样例
见上方表格
算法1
(对顶堆) $O(mnlogn)$
--------> <---------
大根堆 小根堆
大根堆里放A[i - 1]
个元素, 小跟堆放A[i]
以后的元素,取出小根堆的堆顶就是第i
小的数。
时间复杂度
代码注意事项
因为题目给的get
输入是当堆里数的数量达到j - 1
时候的值(即大根堆有j - 1
个数,那么第j
小的数就在小根堆里),所以在代码中直接输出堆顶元素即可。
C++ 代码
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1000010;
int a[N], b[N];
int n, m;
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= m; i ++) cin >> b[i];
sort(b + 1, b + m + 1);
priority_queue<int> left;
priority_queue<int, vector<int>, greater<int>> right;
int i = 1, j = 1;
while (i <= n || j <= m){
while (j <= m && b[j] == i - 1){
//GET操作
cout << right.top() << endl;
left.push(right.top());
right.pop();
j ++;
}
//ADD操作
int x = a[i];
if (left.empty() || x >= right.top()) right.push(x);
else {
left.push(x);
right.push(left.top()); left.pop();
}
i ++;
}
return 0;
}