99클럽 코테 스터디 4일차 TIL-보너스 (이진탐색)

문제 : https://www.acmicpc.net/problem/2512

• Q) 지역별 예산의 상한액 구하기
• 제한조건
  1) 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
  2) 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다.
  3)상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

🚨오늘의 학습

⭐️이진탐색⭐️

지역 예산의 최대값을 이진탐색으로 구현

🗝️지역 예산 최소(left): 0

🗝️지역 예산 최대(right) : 지역별 예산 중 최대값

	int right = Arrays.stream(budgets).max().getAsInt();
    int left =0;
  
        
    while(left<=right){
         int mid = (right+left)/2;
         long sum = 0;
            
         for (int budget : budgets) {
            sum += Math.min(budget, mid);
         }
            
         if(sum<=totalBudget){
            result = mid;
            left = mid+1;  // 지역 예산 상한액 늘리기↑

         }else{
            right = mid-1;
         }
    }