Задача 1: Коровы - в стойла

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

На прямой расположены стойла, в которые необходимо расставить коров так, чтобы минимальное расcтояние между коровами было как можно больше.

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

В первой строке вводятся числа \(N (2<N<10001)\) – количество стойл и \( K (1<K<N) \)– количество коров. Во второй строке задаются \(N\) натуральных чисел в порядке возрастания – координаты стойл (координаты не превосходят \(10^9\))

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

Выведите одно число – наибольшее возможное допустимое расстояние.

Решение:

n, k = map(int, input().split())
*a, = map(int, input().split())
a.sort()
left = 0
right = a[-1] - a[0] + 1
while left < right:
    mid = (left + right)//2
    cows = 1
    last = a[0]
    for cur in a[1:]:
        if cur - last > mid:
            cows += 1
            last = cur
    if cows >= k:
        left = mid+1
    else:
        right = mid
print(left)

Задача 1: Коровы - в стойла

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

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

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

Решение:

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

Пожалуйста, подождите загрузки решения