题解

双指针模拟

考虑 $n$ 为偶数的情况，第一次删除的是原本 $n / 2 - 1$ 的位置的数，第二次删除的是原本 $n / 2$ 的位置的数，第三次删除的是原本 $n / 2 - 2$ 的位置的数.....以此类推。

如果 $n$ 为奇数，删掉 $n / 2$ 的数后变成偶数的情况。

AC代码

问题描述

给定一个长度为 $n$ 的正整数序列，请按照以下规则依次提取序列的中位数并输出：

1. 如果序列的大小为奇数，则中位数是按照升序排序后中间的数字。
2. 如果序列的大小为偶数：
   • 如果排序后中间的两个数字 $x$ 和 $y$ 相等，输出任意一个即可。
   • 如果排序后中间的两个数字 $x$ 和 $y$ 不相等，输出较小的那个数字。

每次输出中位数后，该中位数从序列中删除，并重复上述步骤，直至序列为空。

输入描述

第一行输入一个正整数 $n$，表示序列的长度（$1 \leq n \leq 10^5$）。

第二行输入 $n$ 个正整数，表示序列的元素（$1 \leq a_i \leq 10^9$）。

输出描述

一行输出 $n$ 个整数，表示依次提取出的中位数。

样例输入

4
1 8 9 5

样例输出

5 8 1 9

样例输入

6
6 6 6 6 6 6

样例输出

6 6 6 6 6 6