Minimum Cost of Ropes

Q: Qual è la complessità temporale di Minimum Cost of Ropes?

Tempo O(n log n) e spazio O(n) con un heap minimo: n-1 unioni, ciascuna con tre operazioni sull’heap di O(log n) . Esaminare l’intero mucchio per trovare le due corde più corte richiede invece O(n²) .

FacileHeap Greedy

+10

Hai alcune corde e ropes[i] è la lunghezza della corda i. Puoi unire due corde qualsiasi in un'unica corda la cui lunghezza è la somma delle due, e l'unione costa la stessa somma. Continua a unire le corde finché non ne rimane una sola.

Scrivi una funzione chiamata minCostRopes che restituisca il costo totale minimo per unire tutte le corde in un'unica corda, oppure 0 se inizialmente c'è una sola corda.

Funzione

minCostRopes(ropes: integer-array) → integer

ropesinteger-array: la lunghezza di ciascuna corda
Restituisceinteger: il costo totale minimo per unire tutte le corde in un'unica

Vincoli

1 ≤ ropes.length ≤ 10⁴
1 ≤ ropes[i] ≤ 100
La risposta è rappresentabile in un intero con segno a 32 bit.

Esempi

Input: ropes = [5, 2, 8, 3]
Output: 33
Spiegazione: Unisci 2 e 3 ottenendo 5, le due corde di lunghezza 5 ottenendo 10, poi 8 e 10 ottenendo 18. Il totale è 5 + 10 + 18 = 33.

Input: ropes = [1, 1, 1, 1]
Output: 8
Spiegazione: Unisci gli 1 a coppie al costo di 2 ciascuna, poi unisci le due corde di lunghezza 2 al costo di 4: 8 in totale. Aggiungere ogni 1 a una corda in crescita costerebbe 2 + 3 + 4 = 9.

Per approfondire

Supponiamo che un collegamento possa unire fino a tre corde e costi quanto la loro lunghezza totale. Come cambia la regola greedy quando il numero di corde non è divisibile esattamente?

Soluzione

Ogni unione costa la lunghezza totale di entrambi i pezzi, quindi una corda unita presto viene pagata di nuovo in ogni unione successiva a cui partecipa. Tieni le corde lunghe fuori dalle prime unioni: unisci le due corde più corte a ogni turno. Un heap minimo trova queste due in O(log n).

Cerca i due più corti a ogni turno

Corretto, ma non termina sui test più grandi

Intuizione

A ogni turno, scorri il mucchio per trovare la corda più corta e toglila, scorri di nuovo per trovare la successiva più corta e rimetti nel mucchio la loro giunzione.

Perché proprio le due più corte: rappresenta le giunzioni come un albero, con le corde come foglie. La lunghezza di una corda viene pagata una volta per ogni giunzione che la sovrasta, cioè per la sua profondità. Al livello più profondo ci sono due foglie una accanto all’altra, e spostare lì le due corde più corte non aumenta mai il costo. Quindi esiste un piano ottimale che unisce per prime le due corde più corte, e lo stesso ragionamento si ripete sul mucchio più piccolo.

Ci sono n-1 turni con due scansioni complete: O(n²), circa 10^8 confronti per 10^4 corde.

Algoritmo

Copia le corde in una lista di lavoro, pile, e imposta total a 0.
Ripeti finché non rimane una sola corda: trova la corda più corta e rimuovila spostando l'ultima corda nella sua posizione.
Fai lo stesso di nuovo per ottenere la corda successiva più corta.
Aggiungi la somma delle due a total e aggiungi alla pila una corda di quella lunghezza.
Restituisci 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-heap

Intuizione

Un min-heap mantiene la corda più corta alla radice e rimuovere la radice o inserire una corda ha un costo di O(log n). Un turno consiste in due estrazioni, che ti restituiscono le due corde più corte, e in un inserimento della corda ottenuta unendole.

Per unire n corde servono n-1 operazioni di unione, ciascuna composta da tre operazioni sull’heap, quindi il tempo è O(n log n): circa 4 × 10^5 passaggi per 10^4 corde. L’heap non contiene mai più di n corde.

Algoritmo

Inserisci ogni lunghezza di corda in un min-heap e imposta total = 0.
Ripeti finché non resta una sola corda: estrai le due più corte.
Aggiungi la loro somma a total e reinserisci la somma nell'heap.
Restituisci total, che rimane 0 quando c'era una sola corda.

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

Trappole e casi limite

Ordinare una volta e aggiungere ogni corda a un'unica corda in formazione. La corda in formazione può diventare più lunga delle corde che non hai ancora usato: per [2, 3, 4, 4] il costo è 5 + 9 + 13 = 27, mentre unire le due più corte costa 5 + 8 + 13 = 26.
Scartare la corda unita. La sua lunghezza torna nel mucchio e viene pagata di nuovo in un'unione successiva.
Restituire la lunghezza della corda finale. Per [5, 2, 8, 3] l'ultima corda è lunga 18, ma il costo è 33.
Usare per errore un max-heap. C++ priority_queue e BinaryHeap di Rust restituiscono il valore più grande, a meno che tu non inverta l'ordine.

Domande frequenti3

Qual è la complessità temporale di Minimum Cost of Ropes?

Tempo O(n log n) e spazio O(n) con un heap minimo: n-1 unioni, ciascuna con tre operazioni sull’heap di O(log n). Esaminare l’intero mucchio per trovare le due corde più corte richiede invece O(n²).

Il costo minimo delle corde è uguale alla codifica di Huffman?

Sì, è lo stesso algoritmo. La codifica di Huffman costruisce un codice prefisso unendo ripetutamente i due simboli meno frequenti e minimizza la somma del prodotto di ciascuna frequenza per la sua profondità nell’albero. Qui le corde rappresentano i simboli e le loro lunghezze rappresentano le frequenze, quindi il costo totale è la stessa somma.

È possibile risolvere il problema del costo minimo delle corde senza un heap?

Sì, con due code. Ordina le corde in una coda e inserisci ogni corda unita in fondo a una seconda coda. Le corde unite escono in ordine non decrescente, quindi la corda più corta rimasta si trova in testa a una delle due code. Ogni iterazione richiede quindi O(1) e, con lunghezze fino a 100, un ordinamento per conteggio rende l'esecuzione O(n).

def minCostRopes(ropes):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

ropes = [5, 2, 8, 3]

Output atteso