稳定置顶值题解

稳定置顶值题目链接

题目简述

我们需要维护一个不断增加的数字序列，并支持两种操作：

插入：加入一个新的数值（可能为负数，可能重复）。
查询：求当前序列的中位数。
- 定义：将当前所有数从小到大排序，取排在中间的那个数。
- 特殊情况：如果此时有偶数个数，取中间两个数里靠左（较小）的那一个。

数据范围：，数值范围。

解题思路

这道题是经典的“动态中位数”问题。如果每次查询都排序，复杂度是，总复杂度会炸，所以我们需要一种实时维护顺序的方法。

核心思想：对顶结构（双堆或双Multiset）

我们可以把所有排好序的数字从中间切一刀，分成两部分：

左半部分（较小值集合） ：存放数值较小的那一半。
右半部分（较大值集合） ：存放数值较大的那一半。

为了满足题目“偶数个取靠左”的要求，我们人为规定：

左半部分的数量 必须等于右半部分，或者比右半部分 多 1 个。
这样，左半部分里最大的那个数，就是我们要找的中位数。

工具选择：Multiset vs Priority_queue（堆）

这两种数据结构都可以解决这个问题，核心逻辑是一模一样的：

方案 A：使用 priority_queue (堆) 这是最经典的写法。
- 左半部分用 大根堆（我们要随时拿左边最大的数）。
- 右半部分用 小根堆（我们要随时拿右边最小的数）。
方案 B：使用 multiset (平衡树) 这是本题解和 Standard Code (std) 采用的写法。
- multiset 会自动排序。
- 左半部分（记为 minn）的 rbegin() 就是最大值。
- 右半部分（记为 maxx）的 begin() 就是最小值。
- 优势：multiset 功能更强，支持查找、删除任意元素，且代码写起来很直观。虽然常数比堆稍大，但对于本题的数据量完全足够。

算法流程（配合代码逻辑）

我们用两个 multiset：minn 存左半边，maxx 存右半边。每插入一个数，执行以下三步：

计算左边应有长度：
设当前总数为，根据题目中位数定义，左边（含中位数）应该有的元素个数 lim = (n + 1) / 2。
初步插入：
std 采用了一种“先扔进右边，再调整”的策略。不管是多少，先把它插入右半部分 maxx。
动态调整（关键） ：
- 补齐数量：如果左半部分 minn 的数量少于 lim，就从右半部分 maxx 拿一个最小的扔到左边。
- 维护顺序：此时数量虽然对上了，但可能出现“左边最大的数 > 右边最小的数”的情况（即顺序乱了）。
  - 检测：检查 minn 的最大值和 maxx 的最小值。
  - 交换：如果乱序了，就把这两个数交换位置（左边的去右边，右边的去左边），直到顺序正确。
查询：
直接输出左半部分 minn 的最大值即可。

AC 代码 (C++)

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;

void solve() {
    int q, n = 0; // q是操作次数，n是当前记录的总数字个数
    cin >> q;
    
    // minn 对应思路中的“左半部分”（存较小的一半数）
    // maxx 对应思路中的“右半部分”（存较大的一半数）
    // multiset 会自动将插入的元素从小到大排序
    multiset<int> minn, maxx;
    
    for (int i = 1; i <= q; i++) {
        char c;
        cin >> c; // 读取操作符
        
        if (c == '+') {
            int x;
            cin >> x;
            n++; // 总数量增加
            
            // lim 是左半部分(minn)理论上应该保持的大小
            // 根据中位数定义：(n+1)/2 刚好能处理奇偶情况
            // 比如 n=1->lim=1, n=2->lim=1, n=3->lim=2
            int lim = (n + 1) / 2;
            
            // 1. 先将新元素插入到右半部分
            maxx.insert(x);
            
            // 2. 数量平衡：如果左边不够 lim 个，从右边拿最小的补给左边
            while (minn.size() < lim && maxx.size() > 0) {
                minn.insert(*maxx.begin()); // 取右边最小的放入左边
                maxx.erase(maxx.begin());   // 从右边删除它
            }
            
            // 3. 顺序维护：保证左边的所有数 <= 右边的所有数
            // 如果 左边最大的数 > 右边最小的数，说明这两个数放反了，交换它们
            while (minn.size() > 0 && maxx.size() > 0 && *minn.rbegin() > *maxx.begin()) {
                int leftMax = *minn.rbegin(); // 左边目前最大的
                int rightMin = *maxx.begin(); // 右边目前最小的
                
                // 交换位置
                minn.insert(rightMin);      
                maxx.erase(maxx.begin());   
                
                maxx.insert(leftMax);       
                // 删除左边原来的最大值
                // prev(minn.end()) 获取最后一个元素的迭代器，等同于 rbegin()
                minn.erase(prev(minn.end())); 
            }
        } else {
            // ? 查询操作
            // 根据定义，左半部分的最大值就是当前的中位数
            cout << *minn.rbegin() << endl;
        }
    }
}

signed main() {
    // 开启输入输出加速，应对大数据量的读写
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    
    int t = 1;
    // cin >> t; // 本题没有多组数据，如果有多组取消注释
    while (t--) solve();
    
    return 0;
}

稳定置顶值#题解