변화하는 중간 값

문제 : https://algospot.com/judge/submission/recent/

문제

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

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

코드 ( C ++ ) 종만북 참조

#include <iostream>

#include <queue>

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;

//반복문 불변식

// 1. maxHeap의 크기는 minHeap의 크기와 같거나 1 더 크다.

// 2. maxHeap.top() <= minHeap.top()

// 우선 1번 불변식부터 만족시킨다.

for (int cnt = 1; cnt <= n; ++cnt) {

if (maxHeap.size() == minHeap.size())

maxHeap.push(rng.next());

else

minHeap.push(rng.next());

// 2번 불변식이 깨졌을 경우 복구하자.

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 C;

cin >> C;

while (C--)

{

int N, a, b;

cin >> N >> a >> b;

int ans = runningMedian(N, RNG(a, b));

cout << ans << endl;

}

return 0;

}