题目描述

给定一个长度为 $N$ 的非负整数序列 $A$，对于前奇数项求中位数。

输入格式

第一行一个正整数 $N$。

第二行 $N$ 个正整数 $A_{1\dots N}$。

输出格式

共 $\lfloor \frac{N+1}{2}\rfloor$ 行，第 $i$ 行为 $A_{1\dots 2i-1}$ 的中位数。

样例 #1

样例输入 #1

7
1 3 5 7 9 11 6

样例输出 #1

1
3
5
6

样例 #2

样例输入 #2

7
3 1 5 9 8 7 6

样例输出 #2

3
3
5
6

数据范围与提示

对于 $20\%$ 的数据，$N\le 100$；

对于 $40\%$ 的数据，$N\le 3000$；

对于 $100\%$ 的数据，$1\le N\le 100000$，$0\le A_i\le 10^9$。

题目传送门

完整代码

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> a;
int main() {int n;scanf("%d", &n);for (int i = 1, x; i <= n; i++) {scanf("%d", &x);a.insert(upper_bound(a.begin(), a.end(), x), x);if (i % 2 == 1)printf("%d\n", a[i - 1 >> 1]);}return 0;
}