Minimum Cost of Ropes

Q: Quelle est la complexité temporelle du problème du coût minimal des cordes ?

O(n log n) en temps et O(n) en espace avec un tas min : n-1 assemblages, chacun nécessitant trois opérations sur le tas en O(log n) . Parcourir toute la pile pour trouver les deux cordes les plus courtes donne plutôt une complexité de O(n²) .

FacileTas Glouton

+10

Tu as des cordes, et ropes[i] est la longueur de la corde i. Tu peux joindre deux cordes quelconques pour en former une seule dont la longueur est la somme des deux, et cette jonction coûte cette même somme. Tu continues à les joindre jusqu’à ce qu’il ne reste qu’une seule corde.

Écris une fonction nommée minCostRopes qui renvoie le coût total minimal pour joindre toutes les cordes en une seule, ou 0 s’il n’y a qu’une seule corde au départ.

Fonction

minCostRopes(ropes: integer-array) → integer

ropesinteger-array: la longueur de chaque corde
Renvoieinteger: le coût total minimal pour réunir toutes les cordes en une seule

Contraintes

1 ≤ ropes.length ≤ 10⁴
1 ≤ ropes[i] ≤ 100
La réponse tient dans un entier signé sur 32 bits.

Exemples

Entrée: ropes = [5, 2, 8, 3]
Sortie: 33
Explication: Joignez 2 et 3 pour obtenir 5, les deux cordes de longueur 5 pour obtenir 10, puis 8 et 10 pour obtenir 18. Le total est 5 + 10 + 18 = 33.

Entrée: ropes = [1, 1, 1, 1]
Sortie: 8
Explication: Associe les 1 par paires pour un coût de 2 chacune, puis les deux cordes de longueur 2 pour 4 : 8 au total. Ajouter chaque 1 à une corde qui s’allonge coûterait 2 + 3 + 4 = 9.

Pour aller plus loin

Supposons qu’un raccord puisse joindre jusqu’à trois cordes et coûte la somme de leurs longueurs. Comment la règle gloutonne change-t-elle lorsque le nombre de cordes ne se répartit pas équitablement ?

Solution

Chaque assemblage coûte la longueur totale des deux morceaux, donc une corde assemblée tôt est payée à nouveau à chaque assemblage ultérieur auquel elle participe. Évite d’inclure les longues cordes dans les assemblages précoces : assemble les deux cordes les plus courtes à chaque tour. Un tas min permet de les trouver en O(log n).

Repérez les deux plus courtes à chaque tour

Correcte, mais ne termine pas sur les plus gros tests

Intuition

À chaque tour, parcours le tas pour trouver la corde la plus courte et retire-la, parcours-le à nouveau pour trouver la suivante la plus courte, puis remets leur assemblage dans le tas.

Pourquoi choisir les deux plus courtes : représente les assemblages sous forme d’arbre, avec les cordes comme feuilles. La longueur d’une corde est comptée une fois pour chaque assemblage au-dessus d’elle, ce qui correspond à sa profondeur. Au niveau le plus profond, deux feuilles sont côte à côte, et y déplacer les deux cordes les plus courtes n’augmente jamais le coût. Ainsi, une des stratégies les moins coûteuses consiste à assembler d’abord les deux cordes les plus courtes, et le raisonnement se répète sur le tas réduit.

Il y a n-1 tours comportant deux parcours complets : O(n²), soit environ 10^8 comparaisons pour 10^4 cordes.

Algorithme

Copie les cordes dans une liste de travail, pile, et initialise total à 0.
Répète jusqu’à ce qu’il ne reste qu’une corde : trouve la corde la plus courte et retire-la en déplaçant la dernière corde à sa place.
Fais de même pour obtenir la corde suivante la plus courte.
Ajoute la somme des deux à total et ajoute à la pile une corde de cette longueur.
Renvoie 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

Tas minimum

Intuition

Un tas min-heap conserve la corde la plus courte à sa racine, et retirer la racine ou insérer une corde coûte O(log n). Un tour consiste en deux extractions, qui te donnent les deux cordes les plus courtes, et une insertion de la corde assemblée.

n cordes nécessitent n-1 assemblages de trois opérations sur le tas chacun, donc le temps d’exécution est O(n log n) : environ 4 × 10^5 étapes pour 10^4 cordes. Le tas ne contient jamais plus de n cordes.

Algorithme

Place chaque longueur de corde dans un tas min et définis total = 0.
Répète jusqu’à ce qu’il ne reste qu’une corde : retire les deux plus courtes.
Ajoute leur somme à total et replace la somme dans le tas.
Retourne total, qui reste à 0 lorsqu’il n’y avait qu’une seule corde.

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

Pièges et cas limites

Trier une fois et ajouter chaque corde à une seule corde en cours de formation. La corde en cours peut devenir plus longue que les cordes que tu n’as pas encore utilisées : pour [2, 3, 4, 4], le coût est de 5 + 9 + 13 = 27, tandis que l’assemblage des deux plus courtes coûte 5 + 8 + 13 = 26.
Éliminer la corde assemblée. Sa longueur retourne dans le tas et est à nouveau prise en compte lors d’un assemblage ultérieur.
Renvoyer la longueur de la corde finale. Pour [5, 2, 8, 3], la dernière corde mesure 18, mais le coût est de 33.
Utiliser accidentellement un tas max. En C++, priority_queue et, en Rust, BinaryHeap fournissent la plus grande valeur, sauf si tu inverses l’ordre.

Questions fréquentes3

Quelle est la complexité temporelle du problème du coût minimal des cordes ?

O(n log n) en temps et O(n) en espace avec un tas min : n-1 assemblages, chacun nécessitant trois opérations sur le tas en O(log n). Parcourir toute la pile pour trouver les deux cordes les plus courtes donne plutôt une complexité de O(n²).

Le problème du coût minimal des cordes est-il équivalent au codage de Huffman ?

Oui, c’est le même algorithme. Le codage de Huffman construit un code préfixe en fusionnant encore et encore les deux symboles les moins fréquents, et minimise la somme des fréquences multipliées par leur profondeur dans l’arbre. Ici, les cordes jouent le rôle des symboles et leurs longueurs celui des fréquences, donc le coût total correspond à cette même somme.

Le problème du coût minimum des cordes peut-il être résolu sans tas ?

Oui, avec deux files. Trie les cordes dans une file et ajoute chaque corde assemblée à la fin d’une deuxième file. Les cordes assemblées sortent dans un ordre non décroissant, donc la corde restante la plus courte se trouve à l’avant de l’une des files. Chaque tour prend alors O(1), et avec des longueurs allant jusqu’à 100, un tri par comptage rend l’exécution O(n).

def minCostRopes(ropes):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

ropes = [5, 2, 8, 3]

Résultat attendu