BOJ. Tell Median Value (1655)

BOJ 1655: Say the Middle Number

Maintain the values seen so far in two priority queues. lower is a max-heap containing the lower half, and upper is a min-heap containing the upper half. Keep both invariants:

• Every value in lower is less than or equal to every value in upper.
• lower has either the same number of values as upper, or exactly one more.

For each input value, insert it into the heap whose range it belongs to, then move a root to the other heap if needed to restore the size invariant. The root of lower is then the lower median. When the prefix length is odd, lower has one extra value and its root is the middle element. When the prefix length is even, the two heaps have equal size, and the root of lower is the smaller of the two central values, as required by the problem.

The heaps contain all input values exactly once, so space usage is O(N). Each insertion and possible rebalancing move takes O(log N), giving O(N log N) time overall. Input is read as whitespace-separated integers using a buffered byte reader.

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
  private static final class FastScanner {
    private final BufferedInputStream input = new BufferedInputStream(System.in);
    private final byte[] buffer = new byte[1 << 16];
    private int length = 0;
    private int position = 0;

    private int read() throws IOException {
      if (position == length) {
        length = input.read(buffer);
        position = 0;
        if (length == -1) return -1;
      }
      return buffer[position++];
    }

    int nextInt() throws IOException {
      int c;
      do {
        c = read();
      } while (c <= ' ' && c != -1);

      int sign = 1;
      if (c == '-') {
        sign = -1;
        c = read();
      }
      int value = 0;
      while (c > ' ') {
        value = value * 10 + c - '0';
        c = read();
      }
      return value * sign;
    }
  }

  public static void main(String[] args) throws IOException {
    FastScanner scanner = new FastScanner();
    int n = scanner.nextInt();
    PriorityQueue<Integer> lower =
        new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> upper = new PriorityQueue<>();
    StringBuilder output = new StringBuilder();

    for (int i = 0; i < n; i++) {
      int value = scanner.nextInt();
      if (lower.isEmpty() || value <= lower.peek()) {
        lower.add(value);
      } else {
        upper.add(value);
      }

      if (lower.size() > upper.size() + 1) {
        upper.add(lower.poll());
      } else if (upper.size() > lower.size()) {
        lower.add(upper.poll());
      }
      output.append(lower.peek()).append('\n');
    }

    System.out.print(output);
  }
}