우선순위 큐와 힙 - 변화하는 중간 값

 

우선순위 큐와 힙 - 변화하는 중간 값

 

 

 

 

문제출저 - 알고스팟 https://algospot.com/judge/problem/read/RUNNINGMEDIAN

 

 

 

 

 

 

answer code

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int MOD = 20090711;
int n;
 
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 func(RNG rng) {
    priority_queue<int, vector<int>, less<int>> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    int ret = 0;
 
    // maxHeap = 앞의 절반
    // minHeap = 뒤의 절반
    // 홀수이면 최대 힙에 숫자 하나 더
 
    // maxHeap의 크기는 minHeap의 크기와 같거나 1 더 크다
    // maxHeap.top() <= minHeap.top()
 
    for (int i = 1; i <= n; ++i) {
        if (maxHeap.size() == minHeap.size()) {
            maxHeap.push(rng.next());
        }
        else {
            minHeap.push(rng.next());
        }
 
        // 최대 힙의 원소는 최소 힙의 최소 원소보다 클수가 없다. 복구
        if (!minHeap.empty() && !maxHeap.empty() &&
            minHeap.top() < maxHeap.top()) {
            int a = maxHeap.top(), b = minHeap.top();
            maxHeap.pop();
            minHeap.pop();
            maxHeap.push(b);
            minHeap.push(a);
        }
        ret = (ret + maxHeap.top()) % MOD;
    }
    return ret;
}
 
int main() {
    cin.sync_with_stdio(false);
 
    int T, a, b;
    cin >> T;
 
    while (T--) {
        cin >> n >> a >> b;
        RNG rng(a,b);
        cout << func(rng) << "\n";
    }
}