M21509:序列的中位数

heap, http://cs101.openjudge.cn/practice/21509

思路：大顶堆＋小顶堆

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int num_count;  
    cin >> num_count;
    priority_queue<long long> lower_half;
    priority_queue<long long, vector<long long>, greater<long long>> upper_half;
    for (int i = 1; i <= num_count; ++i) {
        long long current_num; 
        cin >> current_num;
        lower_half.push(current_num);
        if (!upper_half.empty() && lower_half.top() > upper_half.top()) {
            long long temp = lower_half.top();
            lower_half.pop();
            upper_half.push(temp);

            temp = upper_half.top();
            upper_half.pop();
            lower_half.push(temp);
        }
        if (lower_half.size() > upper_half.size() + 1) {
            upper_half.push(lower_half.top());
            lower_half.pop();
        } else if (upper_half.size() > lower_half.size()) {
            lower_half.push(upper_half.top());
            upper_half.pop();
        }
        if (i % 2 == 1) {
            cout << lower_half.top() << endl;  
        }
    }

    return 0;
}