BOJ 1655: 가운데를 말해요

https://www.acmicpc.net/problem/1655

  • 2월동안 187문제 풀기(지난달 누적 87개) (49/187)
  • 유명한 Running Median 문제.
  • 직접 구현한 Heap을 써봄.
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;

class Heap {
  int data[100001];
  int bound;
  int type;

  inline int LS(int a) { return 2*a; }
  inline int RS(int a) { return 2*a+1; }
  inline int PA(int a) { return a/2; }

  inline void swap(int x, int y) {
    int tmp = data[x];
    data[x] = data[y];
    data[y] = tmp;
  }

  inline int max(int x, int y){
    if (type == 0)
      return data[x] > data[y] ? x : y;
    else
      return data[x] < data[y] ? x : y;
  }
  inline int max(int x, int y, int z) {
    return max(x, max(y, z));
  }

 public:
  Heap(int _type) {
    type = _type;
    memset(data, type ? INT_MAX : INT_MIN, sizeof(data));
    bound = 1;
  }

  int size() { return bound-1; }
  int top() { return data[1]; }
  void push(int x) {
    int pos = bound;
    data[bound++] = x;

    while (max(pos, PA(pos)) == pos && pos > 1) {
      swap(pos, PA(pos));
      pos = PA(pos);
    }
  }

  int pop() {
    if (bound == 1) return 0;
    int pos = 1, ret = data[1];
    data[1] = data[--bound];
    data[bound] = type ? INT_MAX : INT_MIN;

    while(LS(pos) < bound || RS(pos) < bound) {
      int m = max(pos, LS(pos), RS(pos));
      if (m == pos) break;
			swap(m, pos);
			pos = m;
    }
    return ret;
  }
};

int N, x;

int main() {
  ios::sync_with_stdio(false);
  cin >> N;
  Heap maxHeap(0), minHeap(1);
  for(int i = 0; i < N; i++) {
    cin >> x;
    if (maxHeap.size() == minHeap.size())
      maxHeap.push(x);
    else
      minHeap.push(x);
    if(minHeap.size() && maxHeap.top() > minHeap.top()) {
      minHeap.push(maxHeap.pop());
      maxHeap.push(minHeap.pop());
    }
    printf("%d\n", maxHeap.top());
  }
}