2696번: 중앙값 구하기

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


$O(tn\lg n)$

두 개의 우선순위 큐 l,r을 준비한다.
a[1...2k-1]의 중앙값을 구하고자 할 때,
a[1...2k-1]을 정렬한 배열을 b[1...2k-1]이라 하면 l은 b[1...k], r은 b[k+1...2k-1]을 가지도록 유지한다.
a[1...2k-1]까지 처리되었고 두 수 x=a[2k], y=a[2k+1]가 추가되었다고 하자.
먼저, l에 x를 추가하고 r에 y를 추가한다.
그리고 l의 최댓값(X)과 r의 최솟값(Y)을 비교하여 X>Y인 경우 두 수를 각각 처음과 다른 우선순위 큐로 옮긴다.
이렇게 하면 위 조건에 맞게 l, r을 유지할 수 있다.

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
int t, m, x, y;
int main() {
    for (scanf("%d", &t); t--;) {
        priority_queue<int> l, r;
        scanf("%d%d", &m, &x);
        l.push(x);
        printf("%d\n%d ", m / 2 + 1, x);
        for (int i = 1, x, y; i <= m / 2; i++) {
            scanf("%d%d", &x, &y);
            l.push(x);
            r.push(-y);
            if ((x = l.top())>(y = -r.top())) {
                l.pop(); l.push(y);
                r.pop(); r.push(-x);
            }
            if (i % 10 == 0) puts("");
            printf("%d ", l.top());
        }
        puts("");
    }
    return 0;
}