Minimum Cost of Ropes

Q: Jaka jest złożoność czasowa problemu Minimum Cost of Ropes?

Czas O(n log n) i pamięć O(n) przy użyciu kopca minimalnego: n-1 połączeń, każde obejmujące trzy operacje na kopcu o złożoności O(log n) . Zamiast tego przeszukiwanie całego stosu w celu znalezienia dwóch najkrótszych lin sprawia, że złożoność wynosi O(n²) .

ŁatweKopiec Algorytmy zachłanne

+10

Masz kilka lin, a ropes[i] to długość liny i. Możesz połączyć dowolne dwie liny w jedną, której długość będzie sumą długości tych lin. Koszt połączenia jest równy tej samej sumie. Łączysz liny, aż zostanie jedna.

Napisz funkcję o nazwie minCostRopes, która zwraca najmniejszy łączny koszt połączenia wszystkich lin w jedną albo 0, jeśli od początku jest tylko jedna lina.

Funkcja

minCostRopes(ropes: integer-array) → integer

ropesinteger-array: długość każdej liny
Zwracainteger: najmniejszy łączny koszt połączenia wszystkich lin w jedną

Ograniczenia

1 ≤ ropes.length ≤ 10⁴
1 ≤ ropes[i] ≤ 100
Odpowiedź mieści się w 32-bitowej liczbie całkowitej ze znakiem.

Przykłady

Wejście: ropes = [5, 2, 8, 3]
Wyjście: 33
Wyjaśnienie: Połącz 2 i 3, otrzymując 5, dwie liny o długości 5, otrzymując 10, a następnie 8 i 10, otrzymując 18. Suma wynosi 5 + 10 + 18 = 33.

Wejście: ropes = [1, 1, 1, 1]
Wyjście: 8
Wyjaśnienie: Łącz 1 w pary, po 2 za każdą, a następnie połącz dwie liny o długości 2 za 4: łącznie 8. Dodanie każdej 1 do jednej wydłużającej się liny kosztowałoby 2 + 3 + 4 = 9.

Pytanie dodatkowe

Załóżmy, że jedno połączenie może łączyć maksymalnie trzy liny i kosztuje tyle, ile wynosi ich łączna długość. Jak zmienia się zachłanna reguła, gdy liczba lin nie dzieli się równo?

Rozwiązanie

Każde łączenie kosztuje tyle, ile wynosi łączna długość obu kawałków, więc za linę połączoną wcześnie płacisz ponownie przy każdym późniejszym łączeniu, w którym bierze udział. Nie łącz długich lin na początku: w każdej rundzie łącz dwie najkrótsze liny. Kopiec minimalny znajduje te dwie w czasie O(log n).

Skanuj w każdej rundzie dwa najkrótsze elementy

Poprawne, ale nie kończy się na największych testach

Intuicja

W każdej rundzie przejrzyj stos, znajdź najkrótszą linę i wyjmij ją, ponownie przejrzyj stos, znajdź kolejną najkrótszą linę i połącz je, a następnie odłóż z powrotem.

Dlaczego dwie najkrótsze: narysuj połączenia jako drzewo, w którym liny są liśćmi. Za długość liny płaci się raz za każde połączenie nad nią, czyli za jej głębokość. Na najgłębszym poziomie znajdują się dwa sąsiadujące liście, a umieszczenie tam dwóch najkrótszych lin nigdy nie zwiększa kosztu. Zatem w jednym z najtańszych planów najpierw łączy się dwie najkrótsze liny, a argument powtarza się dla mniejszego stosu.

Wykonuje się n-1 rund, z których każda obejmuje dwa pełne przeglądy: O(n²), czyli około 10^8 porównań dla 10^4 lin.

Algorytm

Skopiuj liny do listy roboczej pile i ustaw początkową wartość total na 0.
Powtarzaj, aż zostanie jedna lina: znajdź najkrótszą linę i usuń ją, przenosząc ostatnią linę na jej miejsce.
Zrób to samo ponownie, aby znaleźć kolejną najkrótszą linę.
Dodaj sumę długości obu lin do total i dołącz do stosu linę o takiej długości.
Zwróć 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

Min-kopiec

Intuicja

Kopiec minimalny przechowuje najkrótszą linę w swoim korzeniu, a usunięcie korzenia lub wstawienie liny kosztuje O(log n). Jedna runda obejmuje dwa wyjęcia, które dają ci dwie najkrótsze liny, oraz jedno wstawienie połączonej liny.

n lin wymaga n-1 połączeń, po trzy operacje na kopcu każde, więc czas wynosi O(n log n): około 4 × 10^5 kroków dla 10^4 lin. Kopiec nigdy nie przechowuje więcej niż n lin.

Algorytm

Umieść długości wszystkich lin w kopcu minimum i ustaw total = 0.
Powtarzaj, aż zostanie jedna lina: zdejmij dwie najkrótsze.
Dodaj ich sumę do total i wstaw sumę z powrotem do kopca.
Zwróć total, które pozostaje równe 0, jeśli była tylko jedna lina.

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

Pułapki i przypadki brzegowe

Jednorazowe sortowanie i dodawanie każdej liny do jednej bieżącej liny. Bieżąca lina może stać się dłuższa niż liny, których jeszcze nie użyto: dla [2, 3, 4, 4] koszt wynosi 5 + 9 + 13 = 27, podczas gdy połączenie dwóch najkrótszych lin kosztuje 5 + 8 + 13 = 26.
Odrzucenie połączonej liny. Jej długość wraca na stos i zostaje ponownie uwzględniona w kosztach przy późniejszym łączeniu.
Zwrócenie długości końcowej liny. Dla [5, 2, 8, 3] ostatnia lina ma długość 18, ale koszt wynosi 33.
Przypadkowe użycie kopca maksymalnego. C++ priority_queue i Rust BinaryHeap zwracają największą wartość, chyba że odwrócisz kolejność.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu Minimum Cost of Ropes?

Czas O(n log n) i pamięć O(n) przy użyciu kopca minimalnego: n-1 połączeń, każde obejmujące trzy operacje na kopcu o złożoności O(log n). Zamiast tego przeszukiwanie całego stosu w celu znalezienia dwóch najkrótszych lin sprawia, że złożoność wynosi O(n²).

Czy problem minimalnego kosztu lin jest tym samym co kodowanie Huffmana?

Tak, to ten sam algorytm. Kodowanie Huffmana tworzy kod prefiksowy, wielokrotnie łącząc dwa symbole o najmniejszej częstotliwości, i minimalizuje sumę iloczynów częstotliwości każdego symbolu i jego głębokości w drzewie. Tutaj liny odpowiadają symbolom, a ich długości — częstotliwościom, więc całkowity koszt jest tą samą sumą.

Czy problem minimalnego kosztu lin można rozwiązać bez kopca?

Tak, przy użyciu dwóch kolejek. Posortuj liny i umieść je w jednej kolejce, a każdą połączoną linę dodawaj na końcu drugiej. Połączone liny są wyjmowane w kolejności niemalejącej, więc najkrótsza pozostała lina znajduje się na początku jednej z kolejek. Każda runda zajmuje wtedy O(1), a przy długościach do 100 sortowanie przez zliczanie zapewnia złożoność O(n).

def minCostRopes(ropes):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

ropes = [5, 2, 8, 3]

Oczekiwany wynik