Algospot RUNNINGMEDIAN

문제 링크입니다: https://algospot.com/judge/problem/read/RUNNINGMEDIAN

수열의 크기가 정해져있지 않고 초기값과 다음 값의 공식만 주어졌기 때문에 ITES 문제(http://jaimemin.tistory.com/569)처럼 난수 생성기를 통해 숫자를 생성해야하는 문제였습니다.

이후에는 숫자들을 정렬한 뒤 앞의 절반을 최대 힙에, 뒤의 절반을 최소 힙에 넣으면 최대 힙의 root에 중간값이 위치하게 됩니다.

따라서 아래와 같이 불변식을 세웁니다.

1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.(수열의 길이가 홀수일 경우 하나 더 큽니다.)

2. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같다.

runningMedian 함수가 위 두 조건을 만족시키는 것은 코드를 보면 확인할 수 있습니다!

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <functional>

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 result = seed;

                 seed = ((seed*(long long)a) + b) % MOD;

                 return result;

        }

};

 

//힙을 이용해 변화하는 중간 값 문제를 해결하는 함수

int runningMedian(int n, RNG rng)

{

        priority_queue<int, vector<int>, less<int>> maxHeap;

        priority_queue<int, vector<int>, greater<int>> minHeap;

        int result = 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 (!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);

                 }

                 result = (result + maxHeap.top()) % MOD;

        }

        return result;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

                 int N, a, b;

                 cin >> N >> a >> b;

 

                 RNG generator(a, b);

 

                 cout << runningMedian(N, generator) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]