luogu#P1168. 中位数

    ID: 5226 远端评测题 1000ms 128MiB 尝试: 39 已通过: 9 难度: 4 上传者: 标签>二分查找二叉堆快速排序树状数组线段树

中位数

题目描述

给定一个长度为 NN 的非负整数序列 AA,对于前奇数项求中位数。

输入格式

第一行一个正整数 NN

第二行 NN 个正整数 A1NA_{1\dots N}

输出格式

N+12\lfloor \frac{N + 1}2\rfloor 行,第 ii 行为 A12i1A_{1\dots 2i - 1} 的中位数。

7
1 3 5 7 9 11 6
1
3
5
6
7
3 1 5 9 8 7 6
3
3
5
6

提示

对于 20%20\% 的数据,N100N \le 100

对于 40%40\% 的数据,N3000N \le 3000

对于 100%100\% 的数据,1N1000001 \le N ≤ 1000000Ai1090 \le A_i \le 10^9