1. Идея

Нужно выбрать k стойл из n так, чтобы минимальное расстояние между любыми двумя выбранными стойлами было как можно больше.

Здесь удобно использовать поиск по ответу:

• пусть мы проверяем некоторое расстояние d;
• нужно понять, можно ли расставить k коров так, чтобы расстояние между любыми соседними поставленными коровами было не меньше d.

Если для некоторого d это возможно, то для любого меньшего расстояния тоже возможно.
Если для некоторого d это невозможно, то для любого большего тоже невозможно.

Значит, ответ можно искать двоичным поиском.

2. Наблюдения

Наблюдение 1. Стойла нужно отсортировать

Коров ставим в стойла на прямой, поэтому порядок координат важен.
После сортировки можно идти слева направо и жадно выбирать стойла.

Наблюдение 2. Проверка для фиксированного d делается жадно

Хотим проверить, можно ли поставить k коров так, чтобы расстояние между соседними поставленными коровами было не меньше d.

Тогда выгодно:

• первую корову поставить в самое левое стойло;
• каждую следующую — в самое левое из возможных стойл, которое отстоит от предыдущего выбранного хотя бы на d.

Почему это разумно?
Потому что если поставить корову левее, мы оставим больше места для остальных коров справа. Значит, такой жадный способ не ухудшает ответ.

Наблюдение 3. Есть монотонность

Обозначим can(d) — можно ли расставить k коров с минимальным расстоянием хотя бы d.

Тогда:

• если can(d) = true, то can(d - 1) тоже true;
• если can(d) = false, то can(d + 1) тоже false.

Это и позволяет применить двоичный поиск по значению ответа.

3. Алгоритм

1. Считать n, k и координаты стойл.
2. Отсортировать массив координат.
3. Реализовать функцию проверки can_place(d):
   • поставить первую корову в первое стойло;
   • запомнить координату последней поставленной коровы;
   • идти по массиву слева направо;
   • если текущее стойло находится на расстоянии не меньше d от последней поставленной коровы, ставим туда новую корову;
   • если удалось поставить хотя бы k коров, возвращаем true;
   • иначе false.
4. Выполнить двоичный поиск по d:
   • left = 0
   • right = max_coordinate - min_coordinate
   • пока left <= right:
     • mid = (left + right) // 2
     • если can_place(mid) истинно, то такой ответ достижим, пробуем увеличить: сохраняем mid и двигаем left;
     • иначе уменьшаем right.
5. Вывести найденный максимум.

4. Почему это работает

Докажем корректность решения.

Почему жадная проверка правильная

Рассмотрим проверку для фиксированного расстояния d.

Мы ставим первую корову в самое левое стойло, а затем каждую следующую — в первое возможное стойло, которое находится не ближе чем на d от предыдущей.

Нужно понять, почему если таким способом нельзя поставить k коров, то и вообще нельзя.

Идея такая:

• жадный алгоритм всегда ставит очередную корову как можно левее;
• значит, после постановки первых t коров жадный алгоритм не правее любого другого допустимого способа поставить эти t коров;
• следовательно, у жадного алгоритма остаётся не меньше места для оставшихся коров;
• если даже он не смог поставить k коров, никакой другой способ тоже не сможет.

Значит, функция can_place(d) действительно правильно определяет, можно ли получить минимальное расстояние хотя бы d.

Почему двоичный поиск правильный

Пусть can_place(d) истинно. Тогда можно расставить коров с минимальным расстоянием хотя бы d.
Но тогда тем более можно расставить их и с любым меньшим требуемым расстоянием.

Пусть can_place(d) ложно. Тогда нельзя обеспечить расстояние d.
Тем более нельзя обеспечить и любое большее расстояние.

Значит, все значения d разбиваются на две части:

• сначала идут допустимые;
• потом недопустимые.

Именно на такой монотонной функции и работает двоичный поиск, находя максимальное допустимое значение.

5. Сложность

Пусть R = max(x) - min(x).

• Сортировка: O(n log n)
• Одна проверка can_place(d): O(n)
• Количество шагов двоичного поиска: O(log R)

Итоговая сложность:

• O(n log n + n log R)

По памяти:

• O(n) на хранение координат.

Это укладывается в ограничения при n до 2 * 10^5.

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool can_place(const vector<long long>& x, int k, long long d) {
    int placed = 1;
    long long last = x[0];

    for (int i = 1; i < (int)x.size(); i++) {
        if (x[i] - last >= d) {
            placed++;
            last = x[i];
            if (placed >= k) {
                return true;
            }
        }
    }

    return placed >= k;
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<long long> x(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }

    sort(x.begin(), x.end());

    long long left = 0;
    long long right = x.back() - x.front();
    long long answer = 0;

    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (can_place(x, k, mid)) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    cout << answer << '\n';
    return 0;
}

7. Код на Python 3

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

x.sort()

def can_place(d):
    placed = 1
    last = x[0]
    for i in range(1, n):
        if x[i] - last >= d:
            placed += 1
            last = x[i]
            if placed >= k:
                return True
    return placed >= k

left = 0
right = x[-1] - x[0]
answer = 0

while left <= right:
    mid = (left + right) // 2
    if can_place(mid):
        answer = mid
        left = mid + 1
    else:
        right = mid - 1

print(answer)