BOJ 7579: 앱

작성일

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

  • 2월동안 187문제 풀기(지난달 누적 87개) (50/187)
  • 발상의 전환이 필요한 냅색 문제
    • a만큼 A를 썼을 때, 가질수 있는 최대/최소 B를 구하는게 냅색 문제라는 감각이 필요함.
    • 결국 냅색은 0/1이든 무한이든, 몇십만 이내의 좁은 bound를 이용해서 조합의 가능성을 줄이는 일임.
    • 이문제는 두가지로 볼 수 있다.
      • 1) 메모리를 M만큼 쓸때 최대의 cost를 찾기
      • 2) C만큼 cost를 쓸 때 최대의 메모리를 찾기
    • cost의 bound가 더 작으므로 cost로 knapsack을 돌려야함
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());
  }
}