[알고리즘]Algospot_RUNNINGMEDIAN

출처 : https://www.algospot.com/judge/problem/read/RUNNINGMEDIAN

문제

한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다. 예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이지요. 수열의 길이가 짝수일 때는 가운데 있는 두 값 중 보다 작은 것을 수열의 중간값이라고 정의하도록 합시다.

한 수열의 중간값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있습니다. 텅 빈 수열에서 시작해서 각 수가 추가될 때마다 중간값을 계산하는 프로그램을 작성하세요. 예를 들어 3, 1, 5, 4, 2 순서대로 숫자가 추가될 경우 수열의 중간값은 3, 1, 3, 3, 3 순서로 변화합니다.

입력

입력 파일의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 20)가 주어지고, 그 후 C줄에 각 3개의 정수로 수열의 길이 N (1 <= N <= 200,000), 그리고 수열을 생성하는 데 필요한 두 정수 a , b (0 <= a,b <= 10000) 가 주어집니다.

출력

각 테스트 케이스마다 한 줄에 N개의 중간값의 합을 20090711로 나눈 나머지를 출력합니다.

정답코드

#include <bits/stdc++.h>
#define FASTio ios_base ::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'

using namespace std;

const int MOD = 20090711;

struct RNG
{
    int seed, a, b;
    RNG(int _a, int _b) : a(_a), b(_b), seed(1983) {}
    int next()
    {
        int ret = seed;
        seed = ((seed * (long long)a) + b) % MOD;
        return ret;
    }
};

int runningMedian(int n, RNG rng)
{
    priority_queue<int, vector<int>, less<int> > maxHeap;
    priority_queue<int, vector<int>, greater<int> > minHeap;

    int ret = 0;

    for (int cnt = 1; cnt <= n; ++cnt)
    {
        if (maxHeap.size() == minHeap.size())
            maxHeap.push(rng.next());
        else
            minHeap.push(rng.next());

        if (!maxHeap.empty() && !minHeap.empty() && maxHeap.top() > minHeap.top())
        {
            int a = maxHeap.top();
            int b = minHeap.top();
            maxHeap.pop();
            minHeap.pop();
            maxHeap.push(b);
            minHeap.push(a);
        }
        ret = (ret + maxHeap.top()) % MOD;
    }
    return ret;
}

int main()
{
    int t;
    cin >> t;

    while (t--)
    {
        int n, a, b;
        cin >> n >> a >> b;
        int ans = runningMedian(n, RNG(a, b));
        cout << ans << endl;
    }
    return 0;
}

풀이 및 사고과정

priority_queue를 처음 써 봤는데 활용도가 높은 stl 같은 느낌이 들었다. 책의 코드를 따라치고 보면서 이해하려고 노력했다...