题解

双指针模拟

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

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

AC代码

Python

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    a = list(map(int, data[1:]))
    
    a.sort()
    mid = n // 2
    i = mid - (1 - (n % 2))
    j = mid
    
    result = []
    while i >= 0 and j < n:
        result.append(a[i])
        if i != j:
            result.append(a[j])
        i -= 1
        j += 1
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        Arrays.sort(a);
        int mid = n / 2;
        int i = mid - (1 - (n % 2));
        int j = mid;

        StringBuilder result = new StringBuilder();
        while (i >= 0 && j < n) {
            result.append(a[i]).append(" ");
            if (i != j) {
                result.append(a[j]).append(" ");
            }
            i--;
            j++;
        }
        System.out.println(result.toString().trim());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int mid = n >> 1;
    int i = mid - (1 - (n & 1));
    int j = mid;
    
    while (i >= 0 && j < n) {
        cout << a[i] << " ";
        if (i != j) {
            cout << a[j] << " ";
        }
        i--;
        j++;
    }
    return 0;
}

问题描述

给定一个长度为 $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