Minimum Cost of Ropes

Q: Qual é a complexidade de tempo de Minimum Cost of Ropes?

Tempo O(n log n) e espaço O(n) com um min-heap: n-1 junções, cada uma com três operações de heap de O(log n) . Percorrer toda a pilha para encontrar as duas cordas mais curtas resulta em O(n²) .

FácilHeap Guloso

+10

Você tem algumas cordas, e ropes[i] é o comprimento da corda i. Você pode unir quaisquer duas cordas em uma única corda cujo comprimento é a soma dos comprimentos das duas, e essa união custa essa mesma soma. Continue unindo até restar uma única corda.

Escreva uma função chamada minCostRopes que retorne o menor custo total para unir todas as cordas em uma só, ou 0 quando houver apenas uma corda desde o início.

Função

minCostRopes(ropes: integer-array) → integer

ropesinteger-array: o comprimento de cada corda
Retornainteger: o menor custo total para unir todas as cordas em uma só

Restrições

1 ≤ ropes.length ≤ 10⁴
1 ≤ ropes[i] ≤ 100
A resposta cabe em um inteiro com sinal de 32 bits.

Exemplos

Entrada: ropes = [5, 2, 8, 3]
Saída: 33
Explicação: Junte 2 e 3 para obter 5, as duas cordas de comprimento 5 para obter 10, depois 8 e 10 para obter 18. O total é 5 + 10 + 18 = 33.

Entrada: ropes = [1, 1, 1, 1]
Saída: 8
Explicação: Junte os 1 em pares, por 2 cada, depois junte as duas cordas de comprimento 2 por 4: 8 no total. Adicionar cada 1 a uma corda que está crescendo custaria 2 + 3 + 4 = 9.

Para ir além

Suponha que uma junção possa unir até três cordas e custe o comprimento total delas. Como a regra gulosa muda quando o número de cordas não pode ser dividido igualmente?

Solução

Cada junção paga o comprimento total dos dois pedaços, então uma corda unida no início é paga novamente em cada junção posterior da qual participa. Mantenha as cordas longas fora das junções iniciais: junte as duas cordas mais curtas a cada rodada. Um min-heap encontra essas duas em O(log n).

Procure os dois mais curtos a cada rodada

Correta, mas não termina nos maiores testes

Intuição

A cada rodada, examine a pilha para encontrar a corda mais curta e retire-a, examine novamente para encontrar a próxima mais curta e coloque de volta a junção delas.

Por que as duas mais curtas: desenhe as junções como uma árvore, com as cordas como folhas. O comprimento de uma corda é contabilizado uma vez para cada junção acima dela, o que corresponde à sua profundidade. O nível mais profundo tem duas folhas lado a lado, e colocar as duas cordas mais curtas ali nunca aumenta o custo. Portanto, algum plano de menor custo junta primeiro as duas cordas mais curtas, e o argumento se repete na pilha menor.

Há n-1 rodadas com duas varreduras completas: O(n²), cerca de 10^8 comparações para 10^4 cordas.

Algoritmo

Copie as cordas para uma lista de trabalho, pile, e comece com total em 0.
Repita até restar uma corda: encontre a corda mais curta e remova-a movendo a última corda para a posição dela.
Faça o mesmo novamente para obter a próxima corda mais curta.
Adicione a soma das duas a total e acrescente à pilha uma corda com esse comprimento.
Retorne 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

Heap mínimo

Intuição

Um min-heap mantém a corda mais curta em sua raiz, e remover a raiz ou inserir uma corda custa O(log n). Uma rodada consiste em duas extrações, que fornecem as duas cordas mais curtas, e uma inserção da corda unida.

n cordas precisam de n-1 junções, com três operações de heap cada, então o tempo é O(n log n): cerca de 4 × 10^5 etapas para 10^4 cordas. O heap nunca contém mais de n cordas.

Algoritmo

Coloque o comprimento de cada corda em um min-heap e defina total = 0.
Repita até restar uma corda: retire as duas mais curtas.
Adicione a soma delas a total e insira a soma de volta no heap.
Retorne total, que permanece 0 quando havia apenas uma 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

Armadilhas e casos extremos

Ordenar uma vez e adicionar cada corda a uma única corda acumulada. A corda acumulada pode ficar mais longa do que as cordas que você ainda não usou: para [2, 3, 4, 4], o custo é 5 + 9 + 13 = 27, enquanto unir as duas mais curtas custa 5 + 8 + 13 = 26.
Descartar a corda unida. Seu comprimento volta para a pilha e é pago novamente em uma união posterior.
Retornar o comprimento da corda final. Para [5, 2, 8, 3], a última corda tem 18 de comprimento, mas o custo é 33.
Usar acidentalmente um max-heap. A priority_queue do C++ e a BinaryHeap do Rust fornecem o maior valor, a menos que você inverta a ordem.

Perguntas frequentes3

Qual é a complexidade de tempo de Minimum Cost of Ropes?

Tempo O(n log n) e espaço O(n) com um min-heap: n-1 junções, cada uma com três operações de heap de O(log n). Percorrer toda a pilha para encontrar as duas cordas mais curtas resulta em O(n²).

O problema do custo mínimo das cordas é o mesmo que a codificação de Huffman?

Sim, é o mesmo algoritmo. A codificação de Huffman cria um código de prefixo mesclando repetidamente os dois símbolos menos frequentes e minimiza a soma de cada frequência multiplicada por sua profundidade na árvore. Aqui, as cordas representam os símbolos e seus comprimentos representam as frequências, então o custo total é essa mesma soma.

É possível resolver Minimum Cost of Ropes sem um heap?

Sim, com duas filas. Ordene as cordas em uma fila e insira cada corda unida no fim de uma segunda fila. As cordas unidas saem em ordem não decrescente, então a corda mais curta restante está no início de uma das filas. Cada rodada é, então, O(1), e, com comprimentos de até 100, uma ordenação por contagem torna a execução O(n).

def minCostRopes(ropes):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

ropes = [5, 2, 8, 3]

Saída Esperada