RUNNINGMEDIAN

AOJ RUNNINGMEDIAN

Tree, heap

SOL)

수열을 정렬된 상태로 가지고 가면서 중간 값을 결과 값에 더해준다.

단, 수열의 길이가 짝수일 때는 n/2번 째 수를 더해준다.

 

max-heap과 min-heap 쓴다.

 

만약 1부터 10까지의 수를 정렬 한다면 아래와 같이 정렬을 한다.

수열이 하나씩 들어오면 서 발생할 수 있는 경우의 수에 대한 처리는 아래 소스코드에

주석처리 하였음(항상 min-heap의 사이즈가 크거나 같게 운영한다.)

 

[-] Collapse

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

int n, a, b;
vector<int> arr;

int main() {
    int T; scanf("%d", &T);
    while (T--){
        scanf("%d%d%d", &n, &a, &b);
        arr = vector<int>(n);

        arr[0] = 1983;
        for (int i = 1; i < n; i++)
            arr[i] = (arr[i - 1] * (long long)a + b) % 20090711;

        priority_queue<int> minHeap;
        priority_queue<int> maxHeap;

        int sum = 0;
        for (int i = 0; i < n; i++){
            //둘다 비었을 때
            if (minHeap.size() == 0 && maxHeap.size() == 0){
                minHeap.push(-arr[i]);
            }
            //min-heap의 사이즈가 클때
            else if (minHeap.size() > maxHeap.size()){
                //새로 들어오는 수가 min-heap의 top보다 같거나 클때
                if (arr[i] >= -minHeap.top()){
                    //min의 top을 빼고 max에 넣는다. 새로운 수를 min-heap에 추가
                    maxHeap.push(-minHeap.top());
                    minHeap.pop();
                    minHeap.push(-arr[i]);
                }
                //새로 들어오는 수가 min-heap의 top보다 작을경우 max-heap에 넣어준다.
                else {
                    maxHeap.push(arr[i]);
                }
            }
            //min-heap의 사이즈와 max-heap의 사이즈가 같을 때
            else{
                //max-heap의 top값 보다 작을 경우 min-heap에 바로 추가
                if (arr[i] >= maxHeap.top())
                    minHeap.push(-arr[i]);
                //max-heap의 top값 보다 클 경우 빼주고 min에 max의 top을 넣고 pop후
                 새로운 수 max에 추가
                else{
                    minHeap.push(-maxHeap.top());
                    maxHeap.pop();
                    maxHeap.push(arr[i]);
                }
            }

            if ((minHeap.size() + maxHeap.size()) % 2)
                sum = (sum - minHeap.top()) % 20090711;
            else
                sum = (sum + maxHeap.top()) % 20090711;
        }
        printf("%d\n", sum);
    }
    return 0;
}