18110 - solved.ac

 

18110번: solved.ac

 

개 같은 문제 (내 실력이)

 

#include <stdio.h>

const int LN = 3 * 1e5 + 10;

int N, minus; float R;
int ARR[LN];
int minComp(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[LN];
  int (*comp)(int, int);

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

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

    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];
  }
} minq;

void init() {
  minq.init();

  scanf("%d", &N);

  for (int n = 0; n < N; ++n) {
    int t;

    scanf("%d", &t);

    minq.push(t);
  }

  for (int n = 1; n <= N; ++n) {
    ARR[n] = minq.pop();
  }
}

void cal() {
  minus = N * 0.15 + 0.5;

  for (int n = minus + 1; n <= N - minus; ++n) {
    R += ARR[n];
  }
}

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

  init();

  cal();

  int RR = R / (N - 2 * minus) + 0.5;

  if (N) {
    printf("%d", RR);
  } else {
    printf("0");
  }

  return 0;
}

 

힙 + 수학 (c++로 입출력하는 문제 개싫당)