22254 공정 컨설턴트 호석

https://www.acmicpc.net/problem/22254

22254번: 공정 컨설턴트 호석

접근

1. X시간 내에 모든 선물을 완성할 수 있는 최소 라인 수를 요구한다. 1부터 N까지 선형탐색으로 찾을 수 있지만, N이 10만이고, X가 10억이기 때문에 시간 초과가 발생할 수 있다. 따라서 log의 복잡도로 줄이기 위해 이분탐색을 사용해야 한다.

2. 최적해를 찾기 위해서는 가장 작은 라인의 공정 시간 + i번째 선물의 공정 시간으로 계산해야 한다. 따라서 우선순위 큐를 사용했다.

import java.io.*;
import java.util.*;
public class Main {
  public static int N, X, answer = Integer.MAX_VALUE;
  public static int[] dur;
  //limit 개의 공정 라인으로 X시간 내에 제작할 수 있는가?
  public static boolean IsPossible(int limit){
    int max = 0;
    //제작 시간이 가장 작은 라인을 가져오기 위함
    Queue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
      if(o1[0] == o2[0])
        return o1[1] - o2[1];
      return o1[0] - o2[0];
    });

    for(int i = 0; i < limit; i++) {
      int[] arr = {0, 0};
      pq.add(arr);
    }

    for(int i = 0; i < N; i++){
      int[] g = pq.poll();
      g[0] += dur[i];
      max = Math.max(max, g[0]);
      pq.add(g);
    }
    return max <= X;
  }
  public static int BinSearch(){
    int s = 1, e = N, mid;
    while(s <= e){
      mid = (s + e) / 2;
      if(IsPossible(mid)){
        e = mid - 1;
        answer = Math.min(answer, mid);
      }
      else{
        s = mid + 1;
      }
    }
    return answer;
  }
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken()); X = Integer.parseInt(st.nextToken());
    dur = new int[N]; st = new StringTokenizer(br.readLine());
    for(int i = 0; i < N; i++)
      dur[i] = Integer.parseInt(st.nextToken());
    BinSearch();
    System.out.println(answer);
  }
}