题意概括

你需要设计一个数据结构来处理一个持续输入整数的数据流。该数据结构需要支持两种操作：

1. add num: 将一个整数 num 添加到数据结构中。
2. find: 查找并返回当前数据结构中所有元素的中位数。

中位数的定义如下：如果所有元素的个数是奇数，中位数是排序后位于中间的那个数；如果是偶数，则是中间两个数的平均值。

输入格式: 输入包含多行，每行是一种操作，直到文件结束 (EOF)。

输出格式: 对于每个 find 操作，输出一行，包含当前的中位数，结果保留一位小数。

基础知识

对于动态变化的数据集合，要高效地查找中位数，最优的解法是使用 对顶堆 (Two Heaps)。这个结构由两个堆组成，它们协同工作，将数据流巧妙地划分为两部分。

数据结构设计:

1. 一个 大顶堆 (Max-Heap): 用于存储数据流中数值较小的那一半元素。其堆顶元素是这半部分中的最大值。在 C++ 中，priority_queue<int> 默认就是大顶堆。
2. 一个 小顶堆 (Min-Heap): 用于存储数据流中数值较大的那一半元素。其堆顶元素是这半部分中的最小值。在 C++ 中，可以通过 priority_queue<int, vector<int>, greater<int>> 来实现。

核心思想与不变量维护:

为了让中位数始终可以从两个堆的堆顶快速获取，我们必须在每次操作后维持两个核心的 不变量 (Invariants)：

1. 数值关系: 大顶堆中的所有元素都必须小于等于小顶堆中的所有元素。即 max_heap.top() <= min_heap.top()。
2. 数量平衡: 两个堆的大小必须保持平衡。我们规定，它们的数量差不能超过 1。通常，我们让大顶堆的大小等于或比小顶堆多一个元素 (max_heap.size() == min_heap.size() 或 max_heap.size() == min_heap.size() + 1)。

操作实现:

• add num 操作: 为了同时维护上述两个不变量，我们可以采用一个简洁的“先加、再平衡”的策略：

  1. 将新元素 num 压入大顶堆。
  2. 为了维护数值关系，立即将大顶堆的堆顶元素弹出，并压入小顶堆。
  3. 最后，为了维护数量平衡，检查大顶堆的大小是否小于小顶堆。如果是，则从小顶堆弹出堆顶元素，并压入大顶堆。 这一套流程能确保每次添加操作后，两个不变量都得到满足。

• find 操作:

  1. 如果元素总数是奇数，根据我们的数量平衡规则，大顶堆会比小顶堆多一个元素。这个元素就是中位数，即大顶堆的堆顶 max_heap.top()。
  2. 如果元素总数是偶数，两个堆的大小会相等。中位数就是两个堆顶元素的平均值，即 (max_heap.top() + min_heap.top()) / 2.0。

复杂度分析:

• add 操作的时间复杂度为 $O(\log N)$，因为它涉及常数次的堆插入和删除操作。
• find 操作的时间复杂度为 $O(1)$，因为它只需要访问堆顶。
• 空间复杂度为 $O(N)$，用于存储数据流中的所有元素。

C++ 解决方案

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 使用两个优先队列（堆）来维护数据流
priority_queue<int> max_h; // 大顶堆，存较小的一半
priority_queue<int, vector<int>, greater<int>> min_h; // 小顶堆，存较大的一半

// 添加一个数字
void add(int num) {
    max_h.push(num);
    min_h.push(max_h.top());
    max_h.pop();

    // 维持数量平衡：max_h 的大小 >= min_h 的大小
    if (max_h.size() < min_h.size()) {
        max_h.push(min_h.top());
        min_h.pop();
    }
}

// 查找中位数
double find() {
    if (max_h.size() > min_h.size()) {
        // 总数为奇数，中位数在大顶堆顶
        return max_h.top();
    }
    // 总数为偶数，中位数为两个堆顶的平均值
    return (max_h.top() + min_h.top()) / 2.0;
}

int main() {
    // 关闭同步流，加速IO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string op;
    while (cin >> op) {
        if (op == "add") {
            int num;
            cin >> num;
            add(num);
        } else if (op == "find") {
            // 设置输出格式为保留一位小数
            cout << fixed << setprecision(1) << find() << endl;
        }
    }

    return 0;
}

/*
样例输入 1:
add 1
add 2
find
add 3
find

样例输出 1:
1.5
2.0

样例输入 2:
add 6
find
add 10
find
add 2
find
add 6
find

样例输出 2:
6.0
8.0
6.0
6.0
*/