题目描述

给你 1 个空数组 $a$，现在要依次插入 $n$ 个数到数组 $a$ 里面，请在每次插入后输出当前的中位数

• 什么是中位数
• 中位数是指将数组从小到大排序后，处于中间位置的数
  • 比如: a = [1, 2, 3, 4, 5], 中位数是 3
  • 比如: a = [1, 3, 5, 7], 当数组长度是偶数时，中位数是中间 2 个数的均值，此时中位数是 (3 + 5) / 2 = 4

输入格式

第 1 行包含 1 个整数正 $n(1 \le n \le 10^5)$, 表示插入数的个数

接下来 1 行包含 $n$ 个正整数，用空格分开，保证所有的数都是偶数

输出格式

输出 1 行，包含 $n$ 个整数，相邻 2 个数用空格分开，表示每次插入数后，数组的中位数

7
6 8 4 2 12 10 14

6 7 6 5 6 7 8

提示

• 样例解释
• 当 a = [6] 时，中位数是 6
• 当 a = [6,8] 时，中位数是 (6+8)/2=7
• 当 a = [6,8,4] 时，排序后是 [4,6,8]，中位数是 6
• 当 a = [6,8,4,2] 时，排序后是 [2,4,6,8]，中位数是 (4+6)/2=5
• 当 a = [6,8,4,2,12] 时，排序后是 [2,4,6,8,12]，中位数是 6
• 当 a = [6,8,4,2,12,10] 时，排序后是 [2,4,6,8,10,12]，中位数是 (6+8)/2=7
• 当 a = [6,8,4,2,12,10,14] 时，排序后是 [2,4,6,8,10,12,14]，中位数是 8
• 考虑用 2 个 set 来存储数据, s1 存储前一半数, s2 存储后一半数
• 当 a = [6] 时, s1 = {6}, s2 = {}
• 当 a = [6,8] 时, s1 = {6}, s2 = {8}
• 当 a = [6,8,4], s1 = {4, 6}, s2 = {8}
• 当 a = [6,8,4,2], s1 = {2, 4}, s2 = {6, 8}
• 每次新来的数 x, 先将 x 插入 s1, 再把 s1 中最大的数（ 可以用迭代器 s1.rbegin() 获得）插入 s2
• 始终保持 s1 中最大的数, 不超过 s2 中最小的数 , *s1.rbegin() <= *s2.begin()
• 并且 s1.size() 要么等于 s2.size(), 要么等于 s2.size() + 1
• 此时中位数就在 *s1.rbegin() 和 *s2.begin() 中产生
• 当 a = [6,8,4,2,12] 时
  • 先将 12 插入 s1, s1 = {2, 4, 12}, s2 = {6, 8}
  • 再把 s1 中最大的数 12 删除, 插入到 s2, s1 = {2, 4}, s2 = {6, 8, 12}
  • 由于 s1.size() < s2.size(), 于是将 s2 中最小的数 *s2.begin=6 删除, 插入到 s1, s1 = {2, 4, 6}, s2 = {8, 12}
  • 此时中位数是 s1 中最大的数 6

数据规模与限制

• $1 \le n \le 10^5, 1 \le a[i] \le 10^9, a[i] 是偶数$
• 1s, 1024KiB for each test case.

来源

• LCR_160