[JAVA]Programmers入国審査

1617 ワード

問題の説明
n人が並んで入国審査を待っています.入国審査台ごとに審査官が審査するのにかかる時間が異なります.
最初はすべての審査団が空いていました1つの審査台は同時に1人しか審査できない.一番前に立っている人は空いている審査台で審査を受けることができます.しかし、もっと早く終わった審査団があれば、そこで審査を受けるまで待つこともできます.
全員が審査を受けるのに要する時間を最小限に抑えたい.
各レビュー担当者に必要な時間の配列時間をパラメータとしてレビューするときに、すべての人がレビューを受け入れるのに要する時間の最大値を返す解決関数を書いてください.
せいげんじょうけん
入国審査待ち人数は1名以上10000000名以下.
各審査官が1人を審査するのに要する時間は1分以上10000000分以下である.
審査官は1名以上10万名以下です.
I/O例

I/O例説明
最初の二人はすぐに審査を受けに行きます.
7分になると最初の審査団3人目が審査を受けます
10分になると、2番目の審査隊の注釈4人が審査を受けます.
14分になると、最初の審査隊の注釈5人が審査を受けた.
20分になると、2番目の審査台は空いていましたが、6人目はそこで審査を受けず、あと1分待ってから1番目の審査台で審査を受け、28分で全員の審査が終わりました.
import java.util.Arrays;

public class 입국심사 {
	public long solution(int n, int[] times) {
        long answer = 0;
        
        Arrays.sort(times);
        
        long start = 1;	// 심사를 보는데 걸리는 최소 시간 
        long end = n * (long) times[times.length-1]; // 심사를 보는데 걸리는 최대 시간 
         
        
        while(start<=end) {
        	long mid = (start+end)/2;	
        	long cnt = 0;		// 심사관 별로 맡을 수 있는 입국자 수 
        	for(int i=0; i<times.length; i++) {
        		cnt += mid/times[i];
        	}
        	
        	// n보다 작으므로 시간을 늘려야 한다.
        	if(cnt<n) {
        		start = mid + 1;
        	}
        	// n보다 크므로 시간을 줄일 수 있다. 
        	else {
        		end = mid - 1;
        		answer = mid;
        	}
        	
        }
        
        return answer;
    }

}
この問題は二分探索で解いたものだ.まず時間をソートし、所要時間の最小推定値をstart、最大推定値をendに設定します.この探索により,各審査員が審査できる人数を求め,nに比べて最高値を求めた.