# P1168 中位数

## 题目描述

给定一个长度为 $N$ 的非负整数序列 $A$，对于前奇数项求中位数。

## 输入格式

第一行一个正整数 $N$。

第二行 $N$ 个正整数 $A_{1\dots N}$。

## 输出格式

共 $\lfloor \frac{N + 1}2\rfloor$ 行，第 $i$ 行为 $A_{1\dots 2i - 1}$ 的中位数。

##输入输出样例#1

###输入#1

```
7
1 3 5 7 9 11 6
```

###输出#1

```
1
3
5
6
```

##输入输出样例#2

###输入#2

```
7
3 1 5 9 8 7 6
```

###输出#2

```
3
3
5
6
```

## 说明/提示

对于 $20\%$ 的数据，$N \le 100$；

对于 $40\%$ 的数据，$N \le 3000$；

对于 $100\%$ 的数据，$1 \le N ≤ 100000$，$0 \le A_i \le 10^9$。
代码如下
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    priority_queue<int> maxHeap; 
    priority_queue<int, vector<int>, greater<int>> minHeap; 

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        
        if (maxHeap.empty() || x <= maxHeap.top()) {
            maxHeap.push(x);
        } else {
            minHeap.push(x);
        }

        // 调整堆大小：确保maxHeap.size() == minHeap.size() 或 maxHeap.size() == minHeap.size() + 1
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }

        // 奇数项（第1,3,5,...个）时输出中位数
        if (i % 2 == 0) {
            cout << maxHeap.top() << '\n';
        }
    }

    return 0;
}
先读取序列长度 n和序列元素，新元素根据与maxHeap堆顶的大小关系插入对应堆。
调整堆大小：若maxHeap过大，移堆顶到minHeap；若minHeap过大，移堆顶到maxHeap。
输出中位数：每处理完第1、3、5...个元素（下标为偶数），输出maxHeap堆顶（当前中位数）。