白駿1654号「網を切る」

質問する

白駿1654号は網線を切ります

に答える

二分探索問題
二分探索を行った場合,せん断線の個数がn値のとき,右値は行当たりの最大長であった.

Pythonコード

import sys
input = sys.stdin.readline

k, n = map(int, input().split())
line = [int(input()) for _ in range(k)]
left, right = 1, max(line)

while left <= right:
    mid = (left + right) // 2
    tmp = 0
    
    for i in line:
        tmp += i // mid
        
    if tmp >= n:
        left = mid + 1
    else:
        right = mid - 1

print(right)