[2696] 중앙값 구하기

https://www.acmicpc.net/problem/2696

2696번: 중앙값 구하기

중앙값을 포함하는 최소힙, 최소힙에 담기지 않는것들을 전부 넣는 최대힙 두개를 사용하는 잘 알려진 문제

수열이 정렬되었을때, 중앙값이상과 미만으로 두 힙을 넣는다고 생각하면 편하다.

하나씩 넣고, 균형을 잡아주면, 두 우선순위큐의 size가 동일하거나, 중앙값을 포함하는 큐의 size가 하나 더 많다.

동일할때에는 중앙값을 포함하는 힙에 넣고, 그렇지 않으면 반대쪽에 넣는다.

물론, 중앙값을 포함하는 힙의 top()이 그렇지 않는 힙의 top()보다 커야하므로,

매번 넣을때마다 top()끼리 비교해야 한다.

이렇게 자료구조를 매번 균형을 맞춰주면, 최소힙의 top()이 중앙값이 된다.

사실상 "[1655] 가운데를 말해요"와 별반 다를바가 없는 문제이다.​

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

#define sz(x) (int)x.size()

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    int t;

    cin >> t;

    while (t--) {

        priority_queue<int, vector<int>, greater<int>> Q;

        priority_queue<int> q;

        int n, cnt = 0;

        cin >> n;

        cout << (n + 1) / 2 << '\n';

        int i;

        for (i = 0; i < n; i++) {

            int x;

            cin >> x;

            if (sz(q) == sz(Q))

                Q.push(x);

            else

                q.push(x);

            if (!q.empty() && !Q.empty() && q.top() > Q.top()) {

                int a = q.top(), A = Q.top();

                q.pop(), Q.pop();

                q.push(A), Q.push(a);

            }

            if (!(i & 1)) cnt++, cout << Q.top() << ' ';

            if (cnt == 10) cnt = 0, cout << '\n';

        }

        cout << '\n';

    }

    return 0;

}

---