[プログラマー]43238入国審査JAVA

43238入国審査

問題の説明

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

せいげんじょうけん

入国審査待ち人数は1人以上10000000人以下.

審査官1人あたりの審査に要する時間は1分以上10000000分以下である.

審査官1人以上10万人以下.

I/O例

ソースコード

import java.util.Arrays;

public class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);

        long left = 0;
        long right = (long) n * times[times.length - 1];

        while (left <= right) {
            long sum = 0;
            long mid = (left + right) / 2;

            for (int time : times) {
                sum += mid / time;
            }

            if (sum < n) {
                left = mid + 1;
            } else{
                right = mid - 1;
                answer = mid;
            }
        }
        return answer;
    }
}

Comment

問題の範疇で二分探索のヒントを与えるので近づきやすい.

sum += mid / time文を理解すれば簡単に解ける質問.

範囲が広い・최소で答えを探す質問なら、まずこちらの探索を考えてみましょう.