[伯俊/3020]犬糞虫(Java)

Question

問題の説明

Solution

プールアクセス方法

高さによってその高さを決める場合、何個も破壊せずに二分ナビゲーションで

犬糞蜂の移動高さタケノコの高さは32を破壊しないで、33点を通過して34点を通過することができます

正しいコード

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
  static int N, H;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    N = Integer.valueOf(st.nextToken());
    H = Integer.valueOf(st.nextToken());
    // 종유석
    Integer[] top = new Integer[N / 2];
    // 석순
    Integer[] down = new Integer[N / 2];

    int tIdx = 0, dIdx = 0;

    for (int i = 0; i < N; i++) {
      if (i % 2 == 0) {
        down[dIdx++] = Integer.valueOf(br.readLine());
      } else {
        top[tIdx++] = Integer.valueOf(br.readLine());
      }

    }

    Arrays.sort(top);
    Arrays.sort(down);
    int totalObj = down.length;
    int minBreak = Integer.MAX_VALUE;
    int count = 0;

    for (int i = 1; i <= H; i++) {
      // 지나가는 구간이 i 높이일 때
      // 전체 석순 개수 - 통과할 수 있는 개수
      int downBreak = totalObj - passCntByBS(i, down);
      // 전체 종유석 개수 - 통과할 수 있는 개수
      int topBreak = totalObj - passCntByBS(H - i + 1, top);
      int totalBreak = downBreak + topBreak;

      if (totalBreak < minBreak) {
        minBreak = totalBreak;
        count = 1;
      } else if (totalBreak == minBreak) {
        count++;
      }
    }

    bw.write(minBreak + " " + count + " \n");
    bw.flush();
    bw.close();

  }

  static int passCntByBS(int height, Integer[] arr) {
    int start = 0;
    int end = arr.length - 1;
    int maxPass = 0;

    while (start <= end) {
      int mid = (start + end) / 2;

      if (height <= arr[mid]) {
        end = mid - 1;
      } else {
        // 구하는건 몇개를 pass하는지
        // mid는 인덱스 값
        // 만약 0번 idx가 통과 가능한거면 1개가 지나칠 수 있는 것
        maxPass = Math.max(maxPass, mid + 1);
        start = mid + 1;
      }
    }

    return maxPass;
  }

}