Minimum Cost of Ropes

Q: Какова временная сложность задачи «Минимальная стоимость верёвок»?

Сложность по времени — O(n log n) , по памяти — O(n) при использовании минимальной кучи: n-1 объединений, каждое из которых требует трёх операций с кучей за O(log n) . Если вместо этого просматривать всю стопку, чтобы найти два самых коротких каната, сложность составит O(n²) .

ЛегкоКуча Жадные алгоритмы

+10

У вас есть несколько верёвок, и ropes[i] — это длина верёвки i. Вы можете соединить любые две верёвки в одну, длина которой будет равна сумме их длин, а стоимость соединения будет равна той же сумме. Продолжайте соединять верёвки, пока не останется одна.

Напишите функцию с именем minCostRopes, которая возвращает наименьшую общую стоимость соединения всех верёвок в одну или 0, если изначально есть только одна верёвка.

Функция

minCostRopes(ropes: integer-array) → integer

ropesinteger-array: длина каждой верёвки
Возвращаетinteger: минимальная общая стоимость соединения всех верёвок в одну

Ограничения

1 ≤ ropes.length ≤ 10⁴
1 ≤ ropes[i] ≤ 100
Ответ помещается в 32-битное знаковое целое число.

Примеры

Ввод: ropes = [5, 2, 8, 3]
Вывод: 33
Пояснение: Соедини 2 и 3, чтобы получить 5, два каната длиной 5 — чтобы получить 10, затем 8 и 10, чтобы получить 18. Итого: 5 + 10 + 18 = 33.

Ввод: ropes = [1, 1, 1, 1]
Вывод: 8
Пояснение: Соединяй единицы попарно за 2, затем две верёвки длиной 2 за 4: всего 8. Добавление каждой единицы к одной растущей верёвке обошлось бы в 2 + 3 + 4 = 9.

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

Предположим, что соединение может связывать до трёх верёвок и стоит столько, сколько составляет их общая длина. Как изменится жадное правило, если количество верёвок не делится нацело?

Решение

За каждое соединение оплачивается полная длина обеих частей, поэтому за верёвку, соединённую рано, снова платят при каждом последующем соединении, в котором она участвует. Не включай длинные верёвки в ранние соединения: на каждом шаге соединяй две самые короткие верёвки. Мин-куча находит эти две за O(log n).

На каждом раунде ищите две самые короткие

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

Идея

В каждом раунде найди в куче самую короткую верёвку и вынь её, снова просканируй кучу в поисках следующей по длине и верни их соединение обратно.

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

Всего n-1 раундов с двумя полными проходами: O(n²), около 10^8 сравнений для 10^4 верёвок.

Алгоритм

Скопируй верёвки в рабочий список pile и задай начальное значение total равным 0.
Повторяй, пока не останется одна верёвка: найди самую короткую верёвку и удали её, переместив последнюю верёвку на её место.
Сделай то же самое ещё раз, чтобы найти следующую по длине верёвку.
Добавь сумму длин двух верёвок к total и добавь в список верёвку такой длины.
Верни total.

def minCostRopes(ropes):
    pile = list(ropes)

    def take_shortest():
        k = 0
        for i in range(1, len(pile)):
            if pile[i] < pile[k]:
                k = i
        pile[k], pile[-1] = pile[-1], pile[k]  # move it to the end, then remove it
        return pile.pop()

    total = 0
    while len(pile) > 1:
        joined = take_shortest() + take_shortest()
        total += joined
        pile.append(joined)
    return total

Минимальная куча

Идея

Мини-куча хранит самую короткую верёвку в корне, а извлечение корня или вставка верёвки стоит O(log n). Один раунд состоит из двух извлечений, которые дают вам две самые короткие верёвки, и одной вставки соединённой верёвки.

Для соединения n верёвок требуется n-1 соединений, каждое из которых включает три операции с кучей, поэтому время работы составляет O(n log n): примерно 4 × 10^5 шагов для 10^4 верёвок. В куче никогда не хранится больше n верёвок.

Алгоритм

Помести длину каждой верёвки в мин-кучу и установи total = 0.
Повторяй, пока не останется одна верёвка: извлекай две самые короткие.
Добавь их сумму к total и снова помести сумму в кучу.
Верни total, который остаётся равным 0, если была только одна верёвка.

import heapq


def minCostRopes(ropes):
    heap = list(ropes)
    heapq.heapify(heap)  # a min-heap: heap[0] is the shortest rope
    total = 0
    while len(heap) > 1:
        joined = heapq.heappop(heap) + heapq.heappop(heap)
        total += joined
        heapq.heappush(heap, joined)
    return total

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

Однократная сортировка и добавление каждой верёвки к одной накапливаемой верёвке. Накапливаемая верёвка может стать длиннее верёвок, которые вы ещё не использовали: для [2, 3, 4, 4] стоимость составит 5 + 9 + 13 = 27, тогда как соединение двух самых коротких верёвок стоит 5 + 8 + 13 = 26.
Исключение соединённой верёвки. Её длина возвращается в кучу и снова учитывается при следующем соединении.
Возврат длины итоговой верёвки. Для [5, 2, 8, 3] длина последней верёвки равна 18, но стоимость составляет 33.
Случайное использование максимальной кучи. C++ priority_queue и Rust BinaryHeap выдают наибольшее значение, если не изменить порядок.

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

Какова временная сложность задачи «Минимальная стоимость верёвок»?

Сложность по времени — O(n log n), по памяти — O(n) при использовании минимальной кучи: n-1 объединений, каждое из которых требует трёх операций с кучей за O(log n). Если вместо этого просматривать всю стопку, чтобы найти два самых коротких каната, сложность составит O(n²).

Минимальная стоимость соединения верёвок — это то же самое, что кодирование Хаффмана?

Да, это тот же алгоритм. Кодирование Хаффмана строит префиксный код, снова и снова объединяя два наименее часто встречающихся символа, и минимизирует сумму произведений частоты каждого символа на его глубину в дереве. Здесь верёвки играют роль символов, а их длины — частот, поэтому общая стоимость — это та же сумма.

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

Да, с помощью двух очередей. Отсортируй верёвки и помести их в одну очередь, а каждую соединённую верёвку добавляй в конец второй. Соединённые верёвки выходят в неубывающем порядке, поэтому самая короткая из оставшихся верёвок находится в начале одной из очередей. Тогда каждый раунд занимает O(1), а при длинах до 100 сортировка подсчётом обеспечивает время выполнения O(n).

def minCostRopes(ropes):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

ropes = [5, 2, 8, 3]

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