洛谷 P1168 中位数

// 第一反应：每到一个奇数项，就把前面那一段抄出来排一遍序，取正中间那个
//
// 答案永远对，`O(n² log n)`。题面「20% 的数据 N ≤ 100」那一档随便过，
// 顶格 `N = 10⁵` 要排 5 万次、每次平均 5 万个数 —— 第 ② 步量了它到底有多远。

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

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

    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    string out;
    for (int i = 1; i <= n; i += 2) {
        vector<int> v(a.begin() + 1, a.begin() + 1 + i);
        sort(v.begin(), v.end());
        out += to_string(v[i / 2]);
        out += '\n';
    }
    cout << out;
    return 0;
}

// P1168 中位数 —— ★ 这一版就能 AC：**对顶堆**（和隔壁 [P1801] 同一招，节奏不一样）
//
//   L：大根堆，装着较小的那一半；R：小根堆，装着较大的那一半。
//   始终保持 |L| == |R| 或者 |L| == |R| + 1
//   ⇒ 读到第 i 个数（i 为奇数）时 |L| = (i+1)/2，**L 的堆顶就是中位数**。
//
// ============ 和 P1801 的差别：k 长大的节奏 ============
//   [P1801] 每来一次 GET，k 就 +1（而 ADD 来几个由输入说了算）；
//   这道题**每读两个数，k 才 +1** —— 所以这里不用手动搬人，
//   「保持两边一样高」这一条自己就把 k 顶上去了。
//   ⇒ 同一招，两个节奏。**题单把它俩排在一起，恰恰是因为它们不一样。**
//
// ⚠ 只在**奇数项**输出，一共 ⌊(N+1)/2⌋ 行 —— N 是偶数时，最后那个数读进来了但不问。

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

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

    int n;
    if (!(cin >> n)) return 0;

    priority_queue<int> L;                                    // 较小的一半（大根堆）
    priority_queue<int, vector<int>, greater<int>> R;         // 较大的一半（小根堆）
    string out;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (L.empty() || x <= L.top()) L.push(x);
        else R.push(x);

        if (L.size() > R.size() + 1) { R.push(L.top()); L.pop(); }   // L 高了，匀一个过去
        else if (L.size() < R.size()) { L.push(R.top()); R.pop(); }  // R 高了，匀一个回来

        if (i & 1) { out += to_string(L.top()); out += '\n'; }       // ★ 只在奇数项报
    }
    cout << out;
    return 0;
}

// ✗ 错法一：每一项都输出了 —— 题面要的是 ⌊(N+1)/2⌋ 行，只问**奇数项**
//
// 「对于前奇数项求中位数」这句话，读快了就变成「对每一项求中位数」。
// ⚠ 偶数项的中位数本身是没定义的（两个数夹在中间），这一版打的是 L 的堆顶 —— 偏小的那个。
// ★ 官方样例 N = 7：正解 4 行，它 7 行，**一测就死**。

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

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

    int n;
    if (!(cin >> n)) return 0;

    priority_queue<int> L;
    priority_queue<int, vector<int>, greater<int>> R;
    string out;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (L.empty() || x <= L.top()) L.push(x);
        else R.push(x);
        if (L.size() > R.size() + 1) { R.push(L.top()); L.pop(); }
        else if (L.size() < R.size()) { L.push(R.top()); R.pop(); }
        out += to_string(L.top());                 // ⚠ 少了 if (i & 1)
        out += '\n';
    }
    cout << out;
    return 0;
}