1715 - 카드 정렬하기

 

1715번: 카드 정렬하기

 

#include <stdio.h>

typedef long long LL;

const int LN = 1e5 + 10;

int minComp(LL x, LL y) { return x < y; }

void swap(LL& x, LL& y) { LL z = x; x = y; y = z; }

LL R;
int N;
int T;

struct PQ {
  int hn;
  LL heap[LN];
  int (*comp)(LL x, LL y);

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

  void push(LL 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;
    }
  }

  LL 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];
  }
} minpq;

void init() {
  minpq.init();

  scanf("%d", &N);

  for (int n = 0 ; n < N; ++n) {
    scanf("%d", &T);

    minpq.push(T);
  }
}

void calculate() {
  LL a, b;

  while (minpq.hn) {
    a = minpq.pop();

    if (minpq.hn) {
      b = minpq.pop();
  
      minpq.push(a + b);

      R += (a + b);
    }

  }
}

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

  init();

  calculate();

  printf("%lld", R);

  return 0;
}

 

이만치하면 됐다