题意分析

题目给出一个数字序列，要求求出该序列的中位数。

解题思路

解决这个问题的关键就在于排序，因为题目的输入量可能很大，传统的排序方法可能不够，分别用一个大顶堆和一个小顶堆存储这些数字，如果序列长度为奇数，直接弹出大顶堆，即为答案，如果序列长度为偶数，答案为两个堆的堆顶之和取平均。

标程

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    
    priority_queue<unsigned int> left;
    priority_queue<unsigned int, vector<unsigned int>, greater<unsigned int>> right;

    for (int i = 0; i < N; i++) {
        unsigned int x;
        scanf("%u", &x);

        if (left.empty() || x <= left.top()) {
            left.push(x);
        } else {
            right.push(x);
        }

        if (left.size() > right.size() + 1) {
            unsigned int temp = left.top();
            left.pop();
            right.push(temp);
        }
        if (right.size() > left.size()) {
            unsigned int temp = right.top();
            right.pop();
            left.push(temp);
        }
    }

    double median;
    if (N % 2 == 1) {
        median = static_cast<double>(left.top());
    } else {
        median = (static_cast<double>(left.top()) + right.top()) / 2.0;
    }

    printf("%.1f\n", median);
    return 0;
}