最开始有一个长度为 0 0 的序列,需要对序列进行 � n 次操作。每个操作用 p 和 x 两个参数表示: 如果 = 0 p=0,表示向序列中加入 x; 如果 = 1 p=1,表示询问序列从大到小第 x 大的数;没有其他的情况。因为某种特殊性质,每次插入的数一定是从大到小排序后在前 � m 的数。用c++写
时间: 2024-03-03 15:52:46 浏览: 26
以下是使用堆实现的 C++ 代码:
```c++
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int>> q;
int main() {
int n;
cin >> n;
while (n--) {
int op, p, x;
cin >> op >> p >> x;
if (op == 0) {
if (q.size() < p) { // 只保留前 m 大的数
q.push(x);
} else if (x > q.top()) { // 如果 x 比当前最小值大,则删除最小值,并插入 x
q.pop();
q.push(x);
}
} else {
cout << q.top() << endl;
}
}
return 0;
}
```
其中,`priority_queue<int, vector<int>, greater<int>> q` 定义了一个小根堆,`q.top()` 返回堆顶元素,即最小值。在插入元素时,如果堆的大小小于 `m`,则直接插入;如果堆的大小已经为 `m`,则比较插入的元素和堆顶元素的大小,若插入的元素更大,则删除堆顶元素,并插入该元素。