[プログラマー]入国審査
3241 ワード
質問リンク
問題を解く
10億人が10万の入国審査団の中で1つを選ぶのに最大10億分かかる.
非常に驚くべき数字なので、複文で一度に回ることはできません.そこで、この探索を通じて問題を解決しましょう.
この問題を解決するために,二分探索の最左が
絵で表すとそうです.
ここで大切なのは
このような場合、10人のお客さんがいると仮定する簡単な方法があります.もしそうであれば、所定の条件で18名の客を入れることができますが、10名の客しかいないので、mid値が超えていると考えられるので、mid値を減らしましょう.このプロセスでは、二分探索が実行されます.
right値をmid値(=18)に変更すると、その値は減少します.
上記の場合とは逆に、お客様が18人以上の場合は、左の値をmid+1の値に変更します.ここで+1をする理由はよくわかりません
上図の総数はいずれも加算値(=18)であり、nは客数であり、
上のif文には==が含まれていないので、mid値を完全に無視してmid+1を行いますか...?
とにかくこのまま探せばいいのに…でもまだ100%理解してない...
コード#コード#
問題を解く
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
問題解答備考ベルリンクReference
この問題について([プログラマー]入国審査), 我々は、より多くの情報をここで見つけました https://velog.io/@nyanyanyong/프로그래머스-입국심사テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol