[algospot] RUNNINGMEDIAN

문제링크 입니다

🚀 [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로 나눈 나머지를 출력합니다.

🖱 입력 예제

3
10 1 0
10 1 1
10000 1273 4936

💻 출력 예제

19830
19850
2448920

💎 전체 코드는 다음과 같습니다.

//
//  RUNNINGMEDIAN.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/12/23.
//

#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("RUNNINGMEDIAN.txt");
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 runnigMedian(int n, RNG rng){
    priority_queue<int, vector<int>, greater<int> > minHeap;
    priority_queue<int, vector<int>, less<int> > maxHeap;
    int ret = 0;
    for(int i=0; i<n; i++){
        if(minHeap.size() == maxHeap.size()){
            maxHeap.push(rng.next());
        }
        else minHeap.push(rng.next());

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

int main(){
    int test_case;
    fin >> test_case;
    for(int test=0; test<test_case; test++){
        int N, a, b;
        fin >> N >> a >> b;
        RNG rng(a,b);
        cout << runnigMedian(N, rng) << endl;
    }
}