떡볶이 떡 만들기 이취코테 201p

일반적 이분탐색(답이 없으면 상한 또는 하한을 만족 하는 인덱스 혹은 값 반환하도록)

Main.bSearch의

while(left+1<right) 조건으로 인해

L X R의 구조를 지키도록 하여 항상 사이값이 해가 되도록한다.

import java.io.*;
import java.util.StringTokenizer;
import java.util.Arrays;
class Main {
  static int[] data;
  static int N,target;
  
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken()); target = Integer.parseInt(st.nextToken());
    data = new int[N];
    st = new StringTokenizer(br.readLine());
    for (int i=0; i<N; i++){
      data[i] = Integer.parseInt(st.nextToken());
    }
    Arrays.sort(data);
    System.out.println(bSearch());
  }

  public static int bSearch(){
    int left=-1, right = data[N-1];
    while (left+1<right){
      int mid = (left+right)>>1;
      int cur = 0;
      for(int el:data){
        if(el-mid>0) cur+=el-mid;
      }
      if (cur>target) left = mid;
      else if(cur == target) return mid;
      else right=mid;
    }
    return left;
  }

}