https://programmers.co.kr/learn/courses/30/lessons/43238

問題の説明

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

せいげんじょうけん

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

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

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

に答える

最初はなぜかこの探索は感じなかった
この問題は二分探索で時間の最適値を探す問題である.
最も時間が長いのは、n人が仕事が一番遅い審査官を見たことだ.
-> max(times) * n
最小時間は1秒に設定します.
最小時間と最高時間をそれぞれ左、右、中間をmidと呼び、適切なmid値を探します
midは推定時間、すなわち全時間である.
各レビュー担当者が表示できる人数はmid/(各レビュー担当者に必要な時間)
だから一人一人を合わせると、総数の人(人)が見えます.
peopleが所与のnより小さい場合、より多くの時間がかかる.
nより大きい場合は条件は満たされますが、時間を減らして最高価格を探します.

def solution(n, times):
    Min = 1
    Max = max(times)*n
    left, right = Min, Max
    answer = right

    while right >= left:
        people = 0  # 심사관이 심사본 사람 수
        mid = (left + right) // 2
        for t in times:
            # 전체시간(mid) 에서 각 심사관이 본 시간을 나누면 각 심사관이 볼 수 있는 사람수가 되므로 이걸 모두 더해줌
            people += (mid//t)

        if people >= n:  # 주어진 n이 심사 볼 수 있는 사람 수가 보다 적거나 같으면 시간을 줄여야 하므로 right를 mid-1로 해서 시간을 줄이는 쪽으로 범위를 좁힌다
            if answer >= mid:  # n이 people 보다 작은 answer중 최솟값을 찾는다
                answer = mid
            right = mid - 1
        else: # 심사 볼 수  있는 사람이 n보다 적으면 성립이 안되므로 시간을 늘리는 쪽으로 범위를 좁힌다
            left = mid + 1
    return answer