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


質問リンク
問題を解く
10億人が10万の入国審査団の中で1つを選ぶのに最大10億分かかる.
非常に驚くべき数字なので、複文で一度に回ることはできません.そこで、この探索を通じて問題を解決しましょう.
この問題を解決するために,二分探索の最左がleft,最右がright,中間値がmidである.

絵で表すとそうです.
ここで大切なのはmidの価格が24なら.この場合、入国審査隊は2つあり、それぞれ2つと4つの時間がかかります.現在、入国審査隊がそれぞれ必要とする時間2と4midの価格24に分かれている.△一つだけ取ります.

このような場合、10人のお客さんがいると仮定する簡単な方法があります.もしそうであれば、所定の条件で18名の客を入れることができますが、10名の客しかいないので、mid値が超えていると考えられるので、mid値を減らしましょう.このプロセスでは、二分探索が実行されます.
right値をmid値(=18)に変更すると、その値は減少します.
上記の場合とは逆に、お客様が18人以上の場合は、左の値をmid+1の値に変更します.ここで+1をする理由はよくわかりません

上図の総数はいずれも加算値(=18)であり、nは客数であり、
上のif文には==が含まれていないので、mid値を完全に無視してmid+1を行いますか...?
とにかくこのまま探せばいいのに…でもまだ100%理解してない...
コード#コード#
def solution(n, times):
    answer = 0
    
    left = 1
    right = max(times) * n
    
    while left < right:
        mid = (left + right) // 2
        total = 0
        for i in times:
            total += mid // i
        
        if total < n:
            left = mid + 1
        else:
            right = mid
        
    answer = left
    return answer
問題解答備考ベルリンク