Minimum Cost of Ropes

Q: Berapa kompleksitas waktu untuk masalah biaya minimum tali?

Waktu O(n log n) dan ruang O(n) dengan min-heap: n-1 penggabungan, masing-masing memerlukan tiga operasi heap dengan kompleksitas O(log n) . Memindai seluruh tumpukan untuk mencari dua tali terpendek akan membuat kompleksitasnya menjadi O(n²) .

MudahHeap Greedy

+10

Kamu memiliki beberapa tali, dan ropes[i] adalah panjang tali i. Kamu dapat menyambungkan dua tali mana pun menjadi satu tali dengan panjang yang merupakan jumlah panjang keduanya, dan biaya penyambungan itu sama dengan jumlah tersebut. Kamu terus menyambungkan tali hingga tersisa satu tali.

Tulis fungsi bernama minCostRopes yang mengembalikan total biaya terkecil untuk menyambungkan semua tali menjadi satu, atau 0 jika sejak awal hanya ada satu tali.

Fungsi

minCostRopes(ropes: integer-array) → integer

ropesinteger-array: panjang setiap tali
Mengembalikaninteger: total biaya terkecil untuk menyambungkan semua tali menjadi satu

Batasan

1 ≤ ropes.length ≤ 10⁴
1 ≤ ropes[i] ≤ 100
Jawabannya muat dalam bilangan bulat bertanda 32-bit.

Contoh

Input: ropes = [5, 2, 8, 3]
Output: 33
Penjelasan: Gabungkan 2 dan 3 menjadi 5, dua tali dengan panjang 5 menjadi 10, lalu 8 dan 10 menjadi 18. Totalnya adalah 5 + 10 + 18 = 33.

Input: ropes = [1, 1, 1, 1]
Output: 8
Penjelasan: Gabungkan angka 1 secara berpasangan hingga masing-masing panjangnya 2, lalu gabungkan dua tali dengan panjang 2 hingga panjangnya 4: totalnya 8. Menambahkan setiap 1 ke satu tali yang terus memanjang akan memerlukan biaya 2 + 3 + 4 = 9.

Pertanyaan lanjutan

Misalkan satu penyambungan dapat menggabungkan hingga tiga tali dan biayanya sebesar total panjang tali tersebut. Bagaimana aturan greedy berubah ketika jumlah tali tidak terbagi rata?

Solusi

Setiap penggabungan membayar seluruh panjang kedua potongan, jadi tali yang digabung lebih awal akan dibayar lagi dalam setiap penggabungan berikutnya yang melibatkannya. Hindari menggunakan tali panjang dalam penggabungan awal: gabungkan dua tali terpendek setiap putaran. Min-heap menemukan kedua tali tersebut dalam O(log n).

Pindai dua yang paling pendek di setiap putaran

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Pada setiap putaran, cari tali terpendek di tumpukan lalu ambil, cari lagi tali terpendek berikutnya, lalu kembalikan hasil penggabungannya.

Mengapa memilih dua tali terpendek: gambarkan hasil penggabungan sebagai pohon dengan tali sebagai daun. Panjang tali dibayar sekali untuk setiap penggabungan di atasnya, yaitu sebanyak kedalamannya. Tingkat terdalam memiliki dua daun berdampingan, dan menempatkan dua tali terpendek di sana tidak akan menambah biaya. Jadi, salah satu rencana termurah menggabungkan dua tali terpendek terlebih dahulu, lalu argumen yang sama berlaku pada tumpukan yang lebih kecil.

Ada n-1 putaran dengan dua pemindaian penuh: O(n²), sekitar 10^8 perbandingan untuk 10^4 tali.

Algoritma

Salin tali ke dalam list kerja, pile, lalu mulai total dari 0.
Ulangi sampai tersisa satu tali: cari tali terpendek dan hapus dengan memindahkan tali terakhir ke posisinya.
Lakukan hal yang sama lagi untuk mendapatkan tali terpendek berikutnya.
Tambahkan jumlah keduanya ke total, lalu tambahkan tali dengan panjang tersebut ke pile.
Kembalikan 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 minimum

Intuisi

Min-heap menyimpan tali terpendek di akarnya, dan mengambil akar atau memasukkan tali membutuhkan biaya O(log n). Satu putaran terdiri dari dua ekstraksi, yang memberikan dua tali terpendek, dan satu penyisipan tali yang telah disambungkan.

n tali membutuhkan n-1 penyambungan dengan masing-masing tiga operasi heap, jadi waktunya adalah O(n log n): sekitar 4 × 10^5 langkah untuk 10^4 tali. Heap tidak pernah menyimpan lebih dari n tali.

Algoritma

Masukkan setiap panjang tali ke dalam min-heap dan tetapkan total = 0.
Ulangi sampai tersisa satu tali: keluarkan dua tali terpendek.
Tambahkan jumlah panjang keduanya ke total dan masukkan kembali jumlah tersebut ke dalam heap.
Kembalikan total, yang tetap 0 jika hanya ada satu tali.

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

Jebakan dan kasus tepi

Mengurutkan tali sekali, lalu menambahkan setiap tali ke satu tali yang terus bertambah panjang. Tali yang terus bertambah ini bisa menjadi lebih panjang daripada tali yang belum kamu gunakan: untuk [2, 3, 4, 4] biayanya 5 + 9 + 13 = 27, sedangkan menggabungkan dua tali terpendek biayanya 5 + 8 + 13 = 26.
Menghilangkan tali yang sudah digabung. Panjangnya kembali ke tumpukan dan biayanya dihitung lagi pada penggabungan berikutnya.
Mengembalikan panjang tali terakhir. Untuk [5, 2, 8, 3] tali terakhir panjangnya 18, tetapi biayanya 33.
Tidak sengaja menggunakan max-heap. C++ priority_queue dan BinaryHeap Rust memberikan nilai terbesar kecuali kamu membalik urutannya.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk masalah biaya minimum tali?

Waktu O(n log n) dan ruang O(n) dengan min-heap: n-1 penggabungan, masing-masing memerlukan tiga operasi heap dengan kompleksitas O(log n). Memindai seluruh tumpukan untuk mencari dua tali terpendek akan membuat kompleksitasnya menjadi O(n²).

Apakah Biaya Minimum Tali sama dengan pengodean Huffman?

Ya, algoritmanya sama. Pengodean Huffman membangun kode prefiks dengan menggabungkan dua simbol yang paling jarang muncul berulang kali, dan meminimalkan jumlah frekuensi setiap simbol dikalikan dengan kedalamannya di pohon. Di sini, tali berperan sebagai simbol dan panjangnya berperan sebagai frekuensi, sehingga total biayanya adalah jumlah yang sama.

Bisakah Minimum Cost of Ropes diselesaikan tanpa heap?

Ya, dengan dua queue. Urutkan tali ke dalam satu queue dan masukkan setiap tali yang telah disambungkan ke bagian belakang queue kedua. Tali yang telah disambungkan keluar dalam urutan tidak menurun, jadi tali terpendek yang tersisa berada di bagian depan salah satu queue. Setiap putaran kemudian memerlukan O(1), dan dengan panjang hingga 100, counting sort membuat waktu jalannya O(n).

def minCostRopes(ropes):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

ropes = [5, 2, 8, 3]

Output yang diharapkan