クリップローカルエリアネットワーク(決定アルゴリズム)

二分ナビゲーション(決定アルゴリズム)&Gredyアルゴリズム

に質問

クリップローカルエリアネットワーク(決定アルゴリズム)

エリート学院自体はK個のネットワークを持っている.しかし、K個のローカルエリアネットワークの長さはそれぞれ異なる.先生は網の糸を全部N本の同じ長さの網の糸にしたいので、K本の網の糸を切ります.例えば、300センチの網から140センチの網を2本切り取ったら、20センチを捨てるべきだ.(切り取ったケーブルは貼り付けられません.)
便宜上、ローカルネットワーク線を切断する際に失われた長さがなく、既存のK本のローカルネットワーク線でN本のローカルネットワーク線を作成できない場合もないと仮定する.また,トリミング時には常にセンチメートル単位,整数長単位で行うと仮定した.N個よりも多く作られていてN個も含まれています.このとき作成できる最大長線長を求めるプログラムを作成します.
■説明の入力
最初の行はエリート学院がすでに持っているネットワーク線の個数Kと、必要なネットワーク線の個数Nを入力します.Kは1以上10000以下の整数、Nは1以上100000以下の整数である.そして常にK≦Nである.その後,K行において,既に保有している各局所網線の長さはセンチメートル単位の2^31−1以下の自然数で与えられる.
■出力説明
1行目にN本のローカルネットワーク線を生成できる最大長出力はセンチメートル単位の整数である.
■入力例1
4 11
802
743
457
539
■出力例1
200
例示的には、802 cmローカルラインから4個、743 cmローカルラインから3個、457 cmローカルラインから2個、539 cmローカルラインから2個を切り取り、合計11個を生成することができる.

コード#コード#💻

import sys
#sys.stdin=open("input.txt", "rt")  # read text

def Count(len):    # 랜선의 길이로 만들어질 수 있는 랜선의 개수
    cnt = 0
    for x in Line:
        cnt += x // len
    return cnt

k, n = map(int, input().split())
Line = []
res = 0
largest = 0

for i in range(k):
    tmp = int(input())
    Line.append(tmp)
    largest = max(largest, tmp)

lt = 1
rt = largest

while lt <= rt:
    mid = (lt + rt) // 2    # 랜선의 길이
    if Count(mid) >= n:
        res = mid
        lt = mid + 1
    else:
        rt = mid - 1

print(res)

リファレンス

インフラストラクチャ:Pythonアルゴリズム回答