1417 - 국회의원 선거

 

1417번: 국회의원 선거

 

힙 문제

 

#include <stdio.h>

int N;
int T;
int R;

int maxComp(int x, int y) { return x > y; }
void swap(int& x, int& y) { int z = x; x = y; y = z; }

struct PQ {
  int hn;
  int heap[100];
  int (*comp)(int, int);

  void init() {
    hn = 0;
    comp = maxComp;
  }

  void push(int x) {
    heap[++hn] = x;

    for (int c = hn; c > 1; c /= 2) {
      if (comp(heap[c], heap[c / 2])) { swap(heap[c], heap[c / 2]); }
      else break;
    }
  }

  int pop() {
    swap(heap[1], heap[hn--]);

    for (int c = 2; c <= hn; c *= 2) {
      if (c < hn && comp(heap[c + 1], heap[c])) { c++; }
      if (comp(heap[c], heap[c / 2])) { swap(heap[c], heap[c / 2]); }
      else break;
    }

    return heap[hn + 1];
  }
} maxq;

void init() {
  maxq.init();

  scanf("%d", &N);
  scanf("%d", &T);

  for(int n = 0; n < N - 1; ++n) {
    int G;

    scanf("%d", &G);

    maxq.push(G);
  }
}

void calculate() {
  while (maxq.hn && maxq.heap[1] >= T) {
    maxq.push(maxq.pop() - 1);
    R++;
    T++;
  }
}

int main(void) {
  freopen("1417.txt", "r", stdin);

  init();

  calculate();

  printf("%d", R);

  return 0;
}

 

이제 알아서 짜진다