[소프티어] 인증평가 4차 슈퍼컴퓨터 클러스터

문제링크 : https://softeer.ai/practice/info.do?idx=1&eid=1204 

Softeer

이분탐색 문제다

가능한 정답 범위는 0 ~ 20억이다. (N이 1, a1이 10억, B가 10^18일 때)

0~20억 사이의 어떤 값 M을 정답이라 가정하면 N개의 컴퓨터 모두 성능이 M보다 크거나 같아야한다. 

 

N개의 컴퓨터를 모두 확인하면서 M보다 작다면 M에 맞추고, 크다면 무시해도 된다. 

 

N개의 컴퓨터에 대해 위 작업을 했더니 B값으로 모든 컴퓨터에 대해 할당 가능했다면 성공, 아니면 실패다.

 

성공했다는 것은 B값이 넉넉하거나 딱 맞았다는 것이고, 실패했다는 것은 B값이 부족했다는 뜻.

 

* 넉넉하거나 딱 맞았다면 더 높은 값 M이 가능하다는 것이고, 부족했다면 더 낮은 M으로 목표설정을 해야하다는 것이다.

이 M값을 이분탐색을 통해 해결하면 N * log(20억) 이 가능하다. 

 

아래 코드에서처럼 정렬하거나 정답 범위값을 설정하지 않아도 됨.

package softeer;

import java.io.*;
import java.util.*;
public class eid_1204 {
    public static int N;
    public static long M;
    public static long arr[];
    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());
        M = Long.parseLong(st.nextToken());
        st = new StringTokenizer(br.readLine());
        arr = new long[N];
        for(int i = 0;i<N;i++){
            arr[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(arr);
        long start = 0;
        long end = arr[N-1] + (long)Math.sqrt(M);
        long ans = 1000000001;
        while(start <= end){
            //분배 가능한 성능
            long point = M;
            long mid = (start + end) / 2;
            for(int i = 0;i<arr.length;i++){
                if(arr[i] < mid){
                    point-= (mid-arr[i])*(mid-arr[i]);
                }
                if(point<0) break;
            }
            if(point>=0){
                start = mid + 1;
                ans = mid;
            }else{
                end = mid -1;
            }
        }
        System.out.println(ans);
    }
}