## 题目描述给定一个长度为 $N$ 的非负整数序列 $A$，对于前奇数项求中位数。 ## 输入格式第一行一个正整数 $N$。第二行 $N$ 个正整数 $A\_{1\\dots N}$。 ## 输出格式共 $\\lfloor \\frac{N + 1}2\\rfloor$ 行，第 $i$ 行为 $A\_{1\\dots 2i - 1}$ 的中位数。 ## 样例 #1 ### 样例输入 #1 ```markup 7 1 3 5 7 9 11 6 ``` ### 样例输出 #1 ```markup 1 3 5 6 ``` ## 样例 #2 ### 样例输入 #2 ```markup 7 3 1 5 9 8 7 6 ``` ### 样例输出 #2 ```markup 3 3 5 6 ``` ## 提示对于 $20\\%$ 的数据，$N \\le 100$；对于 $40\\%$ 的数据，$N \\le 3000$；对于 $100\\%$ 的数据，$1 \\le N ≤ 100000$，$0 \\le A\_i \\le 10^9$。 ## 题解 ```cpp #include using namespace std; priority_queue> big; // 大根堆 priority_queue, greater> sma; // 小根堆 int absf(int x) { if (x >= 0) return x; else return -x; } int n, t; int main() { cin >> n; scanf("%d", &t); big.push(t); cout << big.top() << endl; for (int i = 2; i <= n; i++) { scanf("%d", &t); if (t > big.top()) sma.push(t); else big.push(t); while (absf(big.size() - sma.size()) > 1) { if (big.size() > sma.size()) { sma.push(big.top()); big.pop(); } else { big.push(sma.top()); sma.pop(); } } if (i % 2 != 0) { if (big.size() > sma.size()) printf("%d\n", big.top()); else printf("%d\n", sma.top()); } } return 0; } ```

树状数组

洛谷P1168 中位数