Chocolate Distribution Problem

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

Сортировка занимает O(n log n) , а сдвиг окна из m пакетов — O(n) , поэтому общая сложность составляет O(n log n) . Для отсортированной копии требуется дополнительная память O(n) , а если сортировать входные данные на месте, то помимо самой сортировки требуется O(1) .

Q: Является ли задача распределения шоколада задачей со скользящим окном?

Да, окно фиксированного размера над отсортированными пакетами. В отличие от окна с текущей суммой, при его перемещении ничего не нужно обновлять: разница для каждого окна — это вычитание первого пакета из последнего.

Q: Можно ли решить задачу о распределении шоколада без сортировки?

Здесь размеры не превышают 10^5 , поэтому сортировка подсчётом упорядочивает их за время O(n + 10^5) , и далее применим тот же слайд. При неограниченных размерах одними сравнениями нельзя добиться сложности лучше O(n log n) : при m = 2 ответ равен 0 тогда и только тогда, когда два пакета равны, а для обнаружения дубликата в худшем случае требуется столько сравнений.

ЛегкоСортировка Скользящее окно

+10

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

Напиши функцию с именем minDifference, которая возвращает наименьшую возможную разницу.

Функция

minDifference(packets: integer-array, m: integer) → integer

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

Ограничения

2 ≤ m ≤ packets.length ≤ 10⁴
1 ≤ packets[i] ≤ 10⁵
В двух упаковках может быть одинаковое количество шоколадок.

Примеры

Ввод: packets = [9, 3, 15, 7, 11, 4]m = 3
Вывод: 4
Пояснение: После сортировки получаем пакеты 3, 4, 7, 9, 11 и 15. И 3, 4, 7, и 7, 9, 11 дают разницу 4, и никакие три пакета не расположены ближе друг к другу.

Ввод: packets = [8, 1, 5]m = 3
Вывод: 7
Пояснение: Есть три ученика и три пакета, поэтому каждый пакет будет выдан, а разница составляет 8 - 1 = 7.

Подсказки

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

Открыто 0 из 3

Решение

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

Исправьте наименьший пакет

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

Идея

Зафиксируй размер самой маленькой раздаваемой упаковки — low. Чтобы размер самой большой упаковки был как можно меньше, возьми m-1 самых маленьких упаковок размером не меньше low. Тогда разница равна размеру m-й по величине упаковки размером не меньше low минус low. Попробуй взять за low размер каждой упаковки, пропусти те варианты, при которых имеется меньше m упаковок такого размера или больше, и выбери наименьшую разницу.

Каждый из n вариантов отбирает и сортирует до n упаковок: O(n² log n). При n = 10^4 различных размерах только на сортировки приходится около 6 × 10^8 сравнений.

Алгоритм

Задайте для best значение, которое не сможет превысить ни один ответ.
Для каждого пакета low соберите все пакеты, в которых не менее low конфет, и отсортируйте их.
Если таких пакетов не менее m, разность между m-м наименьшим значением и low является кандидатом.
Сохраните наименьшего кандидата в best и верните его.

def minDifference(packets, m):
    best = max(packets) - min(packets)  # no gap can be wider than this
    for low in packets:
        # The packets that could go out alongside low, smallest first (low is one of them).
        bigger = sorted(x for x in packets if x >= low)
        if len(bigger) >= m:
            best = min(best, bigger[m - 1] - low)
    return best

Отсортируйте и перемещайте окно из m пакетов

Идея

В отсортированном порядке в окне sizes[i..i+m-1] первым идёт наименьший пакет, а последним — наибольший, поэтому разность равна sizes[i+m-1] - sizes[i].

Оптимальный выбор всегда может быть окном. Если при выборе пропущен пакет, который находится между наименьшим и наибольшим, замените им наибольший пакет. Наименьший остаётся на месте, а наибольший может только уменьшиться, поэтому разность не увеличивается. Повторяйте, пока не останется пропусков.

В первом примере окна из трёх элементов дают 4, 5, 4 и 6, поэтому ответ — 4. Сортировка требует O(n log n), а сдвиг окна — O(n).

Алгоритм

Отсортируй пакеты по возрастанию в sizes.
Установи best равным sizes[m-1] - sizes[0] — первому окну.
Для каждого начального значения i от 1 до n-m сравнивай sizes[i+m-1] - sizes[i] с best и сохраняй меньшее значение.
Верни best.

def minDifference(packets, m):
    sizes = sorted(packets)
    best = sizes[m - 1] - sizes[0]
    # The window sizes[i..i+m-1] holds m packets; its first is the smallest, its last the largest.
    for i in range(1, len(sizes) - m + 1):
        best = min(best, sizes[i + m - 1] - sizes[i])
    return best

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

Завершение окна на i+m вместо i+m-1, из-за чего в нём оказывается m+1 пакетов.
Остановка на одно окно раньше. Начальные позиции идут от 0 до n-m включительно. Для [1, 10, 20, 21] при m = 2 цикл с условием i < n-m пропускает единственную разницу, равную 1.
Пропуск сортировки. В [9, 3, 15, 7, 11, 4] разница между первыми тремя пакетами равна 12, тогда как ответ — 4.
Измерение только первого окна. m наименьших пакетов — один вариант, но лучшая группа может начинаться где угодно.
Сортировка чисел как текста. В JavaScript вызов sort() без компаратора ставит 100000 перед 9.

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

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

Сортировка занимает O(n log n), а сдвиг окна из m пакетов — O(n), поэтому общая сложность составляет O(n log n). Для отсортированной копии требуется дополнительная память O(n), а если сортировать входные данные на месте, то помимо самой сортировки требуется O(1).

Является ли задача распределения шоколада задачей со скользящим окном?

Да, окно фиксированного размера над отсортированными пакетами. В отличие от окна с текущей суммой, при его перемещении ничего не нужно обновлять: разница для каждого окна — это вычитание первого пакета из последнего.

Можно ли решить задачу о распределении шоколада без сортировки?

Здесь размеры не превышают 10^5, поэтому сортировка подсчётом упорядочивает их за время O(n + 10^5), и далее применим тот же слайд. При неограниченных размерах одними сравнениями нельзя добиться сложности лучше O(n log n): при m = 2 ответ равен 0 тогда и только тогда, когда два пакета равны, а для обнаружения дубликата в худшем случае требуется столько сравнений.

def minDifference(packets, m):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

packets = [9, 3, 15, 7, 11, 4]
m = 3

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