(第二份代码不用看了 知道错哪了 i=3的时候输出在前 此时只有两个数字
但是第一份代码不知道怎么错了
[![y0zjJK.png](https://s3.ax1x.com/2021/02/11/y0zjJK.png)](https://imgchr.com/i/y0zjJK)
by AMIRIOX無暝 @ 2021-02-11 09:00:48
@[AMIRIOX無暝](/user/320697) 给你个东西告别手写堆、对顶堆
```cpp
vector<int>vec;
void sort_push(int f)
{
vec.insert(upper_bound(vec.begin(),vec.end(),f),f);
}
```
by wzj_zhzx_oicon @ 2021-02-11 09:26:25
@[AMIRIOX無暝](/user/320697) 告诉你有一个叫 vector 的东西,好用极了,而且常数比 STL 的 priority_queue 快亿倍
by SIXIANG32 @ 2021-02-11 09:30:28
@[AMIRIOX無暝](/user/320697) 把输出放到后面去
by cmll02 @ 2021-02-11 09:32:11
```cpp
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
int n;
priority_queue<int, vector<int>, greater<int> > small;
priority_queue<int, vector<int>, less<int> > big;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
if (!big.empty() && x <= big.top()) {
big.push(x);
} else {
small.push(x);
}
if (small.size() < (small.size() + big.size() + 1) / 2) {
small.push(big.top());
big.pop();
} else if (small.size() > (small.size() + big.size() + 1) / 2) {
big.push(small.top());
small.pop();
}
if (i % 2) {
printf("%d\n", small.top());
}
}
return 0;
}
```
by cmll02 @ 2021-02-11 09:32:47
@[SIXIANG](/user/298549) @[BreakPlus](/user/334727) 然而这题数据范围开大点 vector 就过不去了
by Alan_Zhao @ 2021-02-11 09:33:34
@[SIXIANG](/user/298549) 快亿倍,你确定?
by Remake_ @ 2021-02-11 09:34:19
不懂就问,这个vector不是O(n)的吗
by w23c3c3 @ 2021-02-11 09:41:44
@[Miracle_Creator](/user/223797) 运用了夸张的修辞手法,夸张化了 vector 的常数,使人更加清晰的感受到了 vector 常数之小。(滑稽
by SIXIANG32 @ 2021-02-11 09:49:02
@[w23c3c3](/user/109942) 我记得是 $\sqrt{n}$ 的吧/jk
by SIXIANG32 @ 2021-02-11 09:49:22