1654領域クリップ

質問する

家で暇つぶしをしていたオ·ヨンシクは、朴成元(パク·ソンウォン)の呼び出しを受け、急いで駆けつけた.朴成元. キャンプの時はN本の網線を建設しなければならないが、忙しくて英植に助けを求めた.
呉英植はすでに自分のK本の網線を持っている.しかし、K個のローカルエリアネットワークの長さはそれぞれ異なる.パク・ソンウォンは、網を全部N本の同じ長さの網にしようとしたので、K本の網を切る.例えば、300センチの網から140センチの網を2本切り出すと、20センチになります 捨てるべきだ.(切り取ったケーブルは貼り付けられません.)
便宜上、ローカルエリアネットワークをクリップまたは作成する際に失われた長さがないと仮定し、既存のK本のローカルエリアネットワーク線を使用してN本のローカルエリアネットワーク線を作成できない場合もない.また,トリミング時には常にセンチメートル単位,整数長単位で行うと仮定した.N個よりも多く作られていてN個も含まれています.このとき作成できる最大長線長を求めるプログラムを作成します.

入力

第1行目は、呉英植がすでに保有している網線の個数Kと、必要な網線の個数Nとを入力する.Kは1以上10000以下の整数、Nは1以上100000以下の整数である.そして常にK≦Nである.次に、K行に、既に所有している各ローカルネットワーク線の長さをセンチメートル単位の整数として入力します.ローカルエリアネットワークの長さは231-1の自然数以下である.

しゅつりょく

1行目にN本のローカルネットワーク線を生成できる最大長出力はセンチメートル単位の整数である.

バイナリナビゲーションを使用しないでタイムアウトしたコード

K, N = map(int,input().split())
lines = [int(input()) for _ in range(K)]

lines.sort()
maxv = 0

for i in range(max(lines),0,-1): #자르는 길이: 457부터 1씩 감소됨
    # print(i)
    count = 0
    for j in lines: #갖고 있는 랜선
        cut_line = j//i #2
        count+=cut_line
    if count < N:
        continue
    else:
        maxv=max(maxv,i)
print(maxv)

バイナリ・ナビゲーションを使用するコード

import sys

sys.setrecursionlimit(1000001)

K, N = map(int,input().split())
lines = [int(input()) for _ in range(K)]

lines.sort()
maxLength = 0

def bs(target,start,end):
    global maxLength
    count = 0
    mid = (start+end)//2
    if start>end:
        return None
    for i in lines:
        count+=i//mid
    if count>=target:
        maxLength = max(maxLength,mid)
        return bs(target,mid+1,end)
    elif count<target:
        return bs(target,start,mid-1)

result = bs(N,1,max(lines))
print(maxLength)

注意:

エラー:

が所有しているK本のローカルネットワーク線からそれぞれ切除すべきだと思うので、所有しているローカルネットワーク線の最小長さより小さくはならないと思いますが、N本を製造できれば、必ずしもそれぞれのローカルネットワーク線で切除しなければならないとは限りません.例えば、5 cmを切りたいのですが、4 cmの網があれば5 cmは切れないというわけではありません.4 cmのケーブルさえ使わなければ大丈夫です.

ZeroDivisionError:

を持つK本のローカルエリアネットワーク線の最大長が1の場合、startを0に設定するとmidは0になり、0に分割しようとするとエラーのZeroDivisionErrorが発生します.

N個以上の場合、N個の作成も含まれます.

題に示されるように、Nよりも多く行うこともN個行うことに含まれるので、再帰条件としては「mid値と等しい場合」ではなく「等しいか大きいか」(count>=target)である.

感じ:

最初は無知にバイナリ検索を使って解答を試みなかった.バイナリ探索の概念を知る前に(Two pointerと混同していたので、二つは別の概念)、YouTubeで概念をマスターし、ベースバイナリ探索の問題を解いた後、また解答を再開しました.

は本当にバイナリ探索で解決したいのですが、どの範囲でどの変数をtargetに設定すればいいのか分かりません.これまで解決した探索問題のように,問題上の要求は明確ではない.しかし、やはり最終的に要求される「ローカルネットワーク線の最大長」に焦点を当て、考えてみれば、もちろんtargetになるはずだ.