Aggressive Cows

Q: Какова временная сложность задачи Aggressive Cows?

Сортировка занимает O(n log n) , а двоичный поиск — O(n log D) , где D — расстояние между крайними стойлами, делённое на k-1 . Помимо отсортированной копии, требуется O(1) памяти.

Q: Почему первая корова всегда идет в самое левое стойло?

Возьмите любое подходящее размещение и переместите его самую левую корову в самое левое стойло. Эта корова перемещается только дальше от остальных, поэтому ни одно расстояние не уменьшается, и в одном из оптимальных размещений используется самое левое стойло.

Q: Как распознать бинарный поиск по ответу?

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

СреднеБинарный поиск Сортировка Жадные алгоритмы

+10

Вдоль одной прямой в сарае расположены стойла, а stalls[i] — это позиция стойла i. Все позиции различны и расположены в произвольном порядке. Нужно разместить k коров в k разных стойлах. Коровы дерутся, когда стоят близко друг к другу, поэтому нужно добиться как можно большего расстояния между двумя ближайшими коровами.

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

Функция

aggressiveCows(stalls: integer-array, k: integer) → integer

stallsinteger-array: различные позиции прилавков в любом порядке
kinteger: количество коров, которых нужно разместить
Возвращаетinteger: наибольшее возможное минимальное расстояние между двумя коровами

Ограничения

2 ≤ stalls.length ≤ 5000
0 ≤ stalls[i] ≤ 10⁹
Все позиции в stalls различны.
2 ≤ k ≤ stalls.length

Примеры

Ввод: stalls = [10, 1, 7, 4, 15]k = 3
Вывод: 6
Пояснение: Коровы в стойлах 1, 7 и 15 стоят на расстоянии 6 и 8 друг от друга. Расстояние 7 не подходит: после 1 следующая корова встанет в 10, а стойл на 17 или дальше нет.

Дополнительный вопрос

Что изменится, если киоски расположены по кругу, так что последний киоск в порядке следования также является соседом первого?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

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

Отсортируйте, затем по очереди попробуйте каждый промежуток

Верно, но не успевает на самых больших тестах

Идея

Отсортируй позиции. Тогда две ближайшие коровы всегда будут соседними, поэтому расстояние g подходит, если каждая пара соседних коров находится на расстоянии не меньше g.

Чтобы проверить расстояние, поставь корову в крайнее левое стойло, затем ставь по одной корове в каждое стойло, находящееся не менее чем на g дальше последней коровы. Такое жадное размещение позволяет разместить не меньше коров, чем любое другое. Расположи любое подходящее размещение, начиная слева: корова i в жадном размещении никогда не окажется правее коровы i в этом размещении, поэтому жадный алгоритм найдёт стойло для следующей коровы не позже.

Расстояние 1 всегда подходит, поэтому пробуй g = 2, 3, ... и остановись на первом расстоянии, при котором удаётся разместить меньше k коров. В первом примере при расстоянии 6 удаётся разместить 3 коровы, а при расстоянии 7 — только 2, поэтому ответ — 6.

Если коров две, а стойла находятся в точках 0 и 10^9, потребуется около 10^9 проходов по 5000 стойлам, то есть 5 × 10^12 шагов.

Алгоритм

Отсортируй позиции.
Напиши проверку для зазора g: одна корова в pos[0], затем корова в каждом стойле, где pos[i] - last ≥ g, подсчитывая коров.
Начни с gap = 1.
Пока проверка для gap + 1 размещает как минимум k коров, прибавляй 1 к gap.
Верни gap.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    gap = 1  # positions are distinct, so a gap of 1 always fits every cow
    while cowsPlaced(pos, gap + 1) >= k:
        gap += 1
    return gap

Бинарный поиск по промежутку

Идея

Размещение, в котором каждый промежуток не меньше g+1, также имеет каждый промежуток не меньше g, поэтому результаты проверок идут так: да, ..., да, нет, ..., нет. Бинарный поиск находит последнее «да».

Начинаем поиск с lo = 1, что всегда работает, а hi равно длине отрезка, делённой на k-1 и округлённой вниз: k коров оставляют внутри отрезка k-1 промежутков, поэтому минимальное расстояние не может быть больше. Если проверка проходит, задаём lo = mid, поэтому mid нужно округлять вверх; при округлении вниз значения lo = 5 и hi = 6 будут повторяться бесконечно.

В первом примере длина отрезка равна 14, а k = 3, поэтому hi = 7. Промежуток 4 подходит, промежуток 6 подходит, промежуток 7 не подходит, и диапазон сужается до 6.

Диапазон шириной до 10^9 сужается примерно за 30 проверок по 5000 стойл, то есть примерно за 150 000 шагов.

Алгоритм

Отсортируй позиции.
Установи lo = 1 и hi = (pos[n-1] - pos[0]) / (k-1), округлив вниз.
Пока lo < hi, вычисляй mid = lo + (hi - lo + 1) / 2.
Если при жадной проверке с mid удаётся разместить как минимум k коров, установи lo = mid; иначе установи hi = mid - 1.
Верни lo.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    lo = 1  # positions are distinct, so a gap of 1 always works
    hi = (pos[-1] - pos[0]) // (k - 1)  # k-1 gaps share the whole span
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # round up so lo = mid always moves
        if cowsPlaced(pos, mid) >= k:
            lo = mid  # mid fits, so the answer is mid or larger
        else:
            hi = mid - 1  # mid does not fit, so the answer is smaller
    return lo

Ловушки и крайние случаи

Пропуск сортировки. В неотсортированном массиве [10, 1, 7, 4, 15] с промежутком 6 проверка начинается с 10, не находит более позднего стойла на расстоянии 6 от него и сообщает об одной корове.
Округление mid вниз, когда проход устанавливает lo = mid. Как только hi = lo + 1, диапазон перестаёт сокращаться, и цикл никогда не завершается.
Проверка на точное совпадение с количеством k коров. При промежутке 1 в первом примере размещаются 5 коров — больше, чем 3, — но этот промежуток подходит; проверяйте count ≥ k.
Начало подсчёта коров с 0. Корова в самом левом стойле тоже учитывается, поэтому счёт начинается с 1.

Частые вопросы3

Какова временная сложность задачи Aggressive Cows?

Сортировка занимает O(n log n), а двоичный поиск — O(n log D), где D — расстояние между крайними стойлами, делённое на k-1. Помимо отсортированной копии, требуется O(1) памяти.

Почему первая корова всегда идет в самое левое стойло?

Возьмите любое подходящее размещение и переместите его самую левую корову в самое левое стойло. Эта корова перемещается только дальше от остальных, поэтому ни одно расстояние не уменьшается, и в одном из оптимальных размещений используется самое левое стойло.

Как распознать бинарный поиск по ответу?

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

def aggressiveCows(stalls, k):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

stalls = [10, 1, 7, 4, 15]
k = 3

Ожидаемый вывод