Задача 46: Провода

Условие задачи:

Дано \(N\) отрезков провода длиной \(L_1, L_2, ..., L_N\) сантиметров. Требуется с помощью разрезания получить из них \(K\) равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить \(K\) отрезков длиной даже 1 см, вывести 0.

Ограничения: \(1 <= N <= 10^4\), \(1 <= K <= 10^4\), \(100 <= L_i <= 10^7\), все числа целые.

Входные данные:

В первой строке находятся числа \(N\) и \(K\). В следующих \(N\) строках - \(L_1, L_2, ..., L_N\), по одному числу в строке.

Выходные данные:

Вывести одно число - полученную длину отрезков.

Решение:

n, k = map(int, input().split())

otr = [int(input()) for i in range(n)]


def check(ans):
    s = 0
    otr_l = otr[::]
    for i in range(len(otr_l)):
        while otr_l[i] >= ans:
            otr_l[i] -= ans
            s += 1
        if s >= k:
            break

    return s >= k


l = 0
r = sum(otr) + 1
while r - l > 1:
    m = (r + l) // 2
    if check(m):
        l = m
    else:
        r = m

print(l)

У вас включен блокировщик рекламы. Пожалуйста, выключите его чтобы увидеть решения. На этом сайте не так много рекламы, а кушать что-то надо. Вот котик