[BOJ]1654ローカルエリアネットワークのクリップ(python)

質問する

家で暇つぶしをしていたオ·ヨンシクは、朴成元(パク·ソンウォン)の呼び出しを受け、急いで駆けつけた.朴成元はキャンプの時に使う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本のローカルネットワーク線を生成できる最大長出力はセンチメートル単位の整数である.

に答える

これは簡単な二分探索問題である.
検索範囲を1から最長のローカルエリアネットワーク長に位置決めし、二分探索を開始し、最大のローカルエリアネットワーク長を探せばよい.

import sys

num_exist_cable, num_require_cable = map(int, sys.stdin.readline().split())
exist_cables = []
for i in range(num_exist_cable):
    exist_cables.append(int(sys.stdin.readline()))

min_len, max_len = 1, max(exist_cables)
while min_len <= max_len:
	# 이분 탐색 위한 중간값
    cut = (min_len+max_len) // 2
    num_cables = 0
    for cable in exist_cables:
        num_cables += cable // cut
    # 덜 잘라도 될 경우 더 긴 길이 범위에 대해서 자름
    if num_cables >= num_require_cable:
        min_len = cut+1
    # 더 잘라야 될 경우 짧은 길이 범위에 대해서 자름
    else:
        max_len = cut-1
print(max_len)