PS/종만북

[RUNNINGMEDIAN] 변화하는 중간 값

YongHoonJJo 2018. 7. 20. 01:58

[RUNNINGMEDIAN] 변화하는 중간 값 : https://algospot.com/judge/problem/read/RUNNINGMEDIAN


### 우선순위 큐 (힙) ###


<소스코드>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
typedef long long int lli;
const lli MOD = 20090711LL; 
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n, b;
        lli a;
        scanf("%d%lld%d", &n, &a, &b);
 
        lli ai = 1983LL;
        lli ans = ai;
        priority_queue<lli> minH, maxH;
        maxH.push(ai);
        for(int i=1; i<n; i++) {
            ai = (1LL*ai*a+b)%MOD; 
            
            if(i&1) minH.push(-ai);
            else maxH.push(ai);
           
            if(-minH.top() < maxH.top()) {
                int a = maxH.top(); maxH.pop();
                int b = -minH.top(); minH.pop();
                maxH.push(b);
                minH.push(-a);
            }
            ans = (ans + maxH.top()) % MOD;
       }
        printf("%lld\n", ans);
    }
    return 0;
}
 
cs


>> 맥스힙에는 중간값 기준으로 중간값 포함, 그보다 작은 것들을, 민힙에는 중간값보다 큰 녀석들이 들어가게 된다.