[algospot] 변화하는 중간 값 (c++)

출처 : algospot.com :: RUNNINGMEDIAN

algospot.com :: RUNNINGMEDIAN

풀이 방법

문제의 핵심은 우선순위 큐를 두개를 이용하여 중간 값을 찾는 것이다.

하나는 최대 힙 하나는 최소 힙으 이용하여 최대 힙의 최대 원소가 최소 힙의 최소 원소보다 작거나 같게 만들고,

최대 힙의 원소 개수가 최소 힙의 원소 개수 보다 

+1 크거나 같게 유지시켜주며 원소를 삽입시키면 중간 값은 최대 힙의 최댓값이 될 것이다.

#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()		
	for (int cnt = 1; cnt <= n; ++cnt) {
		// 우선 1번 불변식부터 만족시킨다.
		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;		
		cout << runningMedian(N,RNG(a, b)) << endl;
	}
	return 0;
}

//코드 출처 : 알고리즘 문제해결전략