入国審査

質問する

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

せいげんじょうけん

入国審査待ち人数は10000000人を超えない.

各レビュー担当者が1人の従業員をレビューするのに要する時間は、1分当たり10000000分を超えない.

1名以上の審査員は100000名を下回っている.

I/O例

ntimes6[7, 10]

I/O例説明

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

問題を解く

失敗した解答

import bisect
def solution(n, times):
    answer = 0
    time=[]
    
    for i in range(1,n+1):
        for j in range(len(times)):
            time.append(times[j]*i)
    
    time.sort()
    
    return time[n-1]

二分探索問題なのでタイムアウトが発生しました.
成功した解答

def solution(n, times):
    answer = 0
    left=min(times)
    right=max(times)*n

    while left<=right:
        cnt=0
        mid=(left+right)//2
        for t in times:
            cnt+=mid//t

        if cnt<n:
            left=mid+1
        elif cnt>=n:
            right=mid-1
            answer=mid

    return answer

二分探索の方法で問題を解く.
一人一人が審査を受けるのに最小限の時間を稼ぐため、すべての審査台で得られる人数を探し、二分探索を行う.
すなわち,中間値をレビューテーブルに分割するのに要する時間を決定し,最大何人がレビューを受け入れることができるかを決定し,n명がレビューを受け入れることができるかどうかを判断する.n명このレビューを受け入れられない場合は、範囲を増やすことができます.n명レビューが受け入れられる場合は、値がリフレッシュされ、範囲が縮小されます.

エラーコード

if cnt<=n:
	left=mid+1
else:
    right=mid-1

書き始めたばかりで、失敗して、直すところを見つけました.if文のみで条件を分割し、left、rightを更新し、例の問題でmid==29であっても条件を通過する.
この部分では、私はついに他の人の解答を参考にする必要があることに気づき、すべてのn명が審査を受けることができるかどうかを考えました.また、cnt==nであれば考慮されるため、answer=midに更新される.
二分探索法は知られているが,この問題に適用するのは難しい.最小の時間値を目指して二分探索を行うのではなく、最大で審査を受けられる人数nの時間値を探し出すので、想像しにくい.最後に他の人の解答を見て勉強する問題練習を重ねてこそ慣れるようです.