[ALGOSPOT] 변화하는 중간값 (RUNNINGMEDIAN)

algospot.com/judge/problem/read/RUNNINGMEDIAN

algospot.com :: RUNNINGMEDIAN

<문제>

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

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

입력 생성

입력의 크기가 큰 관계로, 이 문제에서는 수열을 입력받는 대신 다음과 같은 식을 통해 프로그램 내에서 직접 생성합니다.

• A[0] = 1983
• A[i] = (A[i-1] * a + b) % 20090711

a와 b는 입력에 주어지는 상수입니다. 이 문제의 해법은 입력을 생성하는 방식과는 아무 상관이 없습니다.

 

<입력>

입력 파일의 첫 줄에는 테스트 케이스의 수 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

 

<아이디어>

백준 온라인 저지에 거의 같은 문제가 있음.

어떤 오름차순으로 정렬된 배열이 있다고 하자. 이 배열을 반으로 나눠 왼쪽 부분을 최대 힙, 오른쪽 부분을 최소 힙에 넣는다.

그렇게 하면 최대 힙에서 top 값과 최소 힙에서 top 값은 중간에서 만나는 값이 된다.

 

 

#include <bits/stdc++.h>
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
using namespace std;
typedef long long lld;
 
struct random_number_generator
{
    lld seed, a, b;
    random_number_generator()
    {
        seed = 1983;
        a = 0;
        b = 0;
    }
    random_number_generator(lld a, lld b)
    {
        seed = 1983;
        this->a = a;
        this->b = b;
    }
    lld next()
    {
        lld ret = seed;
        seed = (seed * a + b) % 20090711;
        return ret;
    }
};
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int tc;
    cin>>tc;
    while(tc--)
    {
        int n;
        lld a, b;
        cin>>n>>a>>b;
        random_number_generator rng(a, b);
        priority_queue<lld, vector<lld>, less<lld>> left;
        priority_queue<lld, vector<lld>, greater<lld>> right;
        lld ans = 0;
        while(n--)
        {
            if(left.size() == right.size()) left.push(rng.next());
            else right.push(rng.next());
            if(!left.empty() && !right.empty() && left.top() > right.top())
            {
                lld a = left.top(), b = right.top();
                left.pop();
                right.pop();
                left.push(b);
                right.push(a);
            }
            ans = (ans+left.top()) % 20090711;
        }
        cout<<ans<<endl;
    }
 
    return 0;
}