Minimum Cost of Ropes

Q: Halatların Minimum Maliyetinin zaman karmaşıklığı nedir?

O(n log n) zaman ve O(n) alan kullanımı; bir min-heap ile: n-1 birleştirme, her biri O(log n) olan üç yığın işlemi. Bunun yerine en kısa iki halatı bulmak için tüm yığını taramak, karmaşıklığı O(n²) yapar.

KolayYığın (heap)Açgözlü

+10

Bazı iplerin var ve ropes[i], i. ipin uzunluğudur. Herhangi iki ipi, uzunluğu bu ikisinin toplamına eşit olan tek bir ipte birleştirebilirsin ve bu birleştirme aynı toplam kadar maliyetlidir. Geriye tek bir ip kalana kadar birleştirmeye devam edersin.

Tüm ipleri tek bir ipte birleştirmenin toplam maliyetinin en küçüğünü döndüren minCostRopes adlı bir fonksiyon yaz; başta yalnızca bir ip varsa 0 döndür.

Fonksiyon

minCostRopes(ropes: integer-array) → integer

ropesinteger-array: her bir ipin uzunluğu
Döndürürinteger: her ipi tek bir ip hâline getirmenin en düşük toplam maliyeti

Kısıtlar

1 ≤ ropes.length ≤ 10⁴
1 ≤ ropes[i] ≤ 100
Yanıt, 32 bitlik işaretli bir tamsayıya sığar.

Örnekler

Girdi: ropes = [5, 2, 8, 3]
Çıktı: 33
Açıklama: 5 elde etmek için 2 ve 3'ü birleştir, 5 uzunluğundaki iki ipi birleştirerek 10 elde et, ardından 18 elde etmek için 8 ve 10'u birleştir. Toplam 5 + 10 + 18 = 33.

Girdi: ropes = [1, 1, 1, 1]
Çıktı: 8
Açıklama: 1’leri ikişerli olarak birleştirip her biri için 2 ödeyin, ardından uzunluğu 2 olan iki ipi 4’e birleştirin: toplam 8. Her bir 1’i giderek uzayan tek bir ipe eklemek 2 + 3 + 4 = 9 tutardı.

Ek soru

Birleştirmenin en fazla üç ipi birleştirebildiğini ve maliyetinin toplam uzunlukları olduğunu varsayalım. İp sayısı eşit bölünmediğinde açgözlü kural nasıl değişir?

Çözüm

Her bir birleştirme, iki parçanın da tam uzunluğu kadar maliyet getirir; bu yüzden erken birleştirilen bir ipin maliyeti, yer aldığı sonraki her birleştirmede yeniden ödenir. Uzun ipleri erken birleştirmelerden uzak tut: her turda en kısa iki ipi birleştir. Bir min-yığın bu ikisini O(log n) sürede bulur.

Her turda en kısa iki tanesini tara

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Her turda, yığındaki en kısa halatı bulup çıkarın, bir sonraki en kısa halatı bulmak için yeniden tarayın ve bu ikisinin birleşimini geri koyun.

Neden en kısa iki halat: Birleşimleri, halatların yaprak olduğu bir ağaç olarak çizin. Bir halatın uzunluğu, üzerindeki her birleşim için bir kez ödenir; bu da halatın derinliğidir. En derin seviyede yan yana iki yaprak bulunur ve en kısa iki halatı oraya taşımak maliyeti hiçbir zaman artırmaz. Dolayısıyla en ucuz planlardan biri önce en kısa iki halatı birleştirir ve aynı gerekçe daha küçük yığın üzerinde tekrarlanır.

İki tam taramadan oluşan n-1 tur vardır: O(n²), 10^4 halat için yaklaşık 10^8 karşılaştırma.

Algoritma

Halatları pile adlı çalışma listesine kopyalayın ve total değerini 0 olarak başlatın.
Bir halat kalana kadar tekrarlayın: en kısa halatı bulun ve son halatı onun yerine taşıyarak halatı kaldırın.
Bir sonraki en kısa halatı bulmak için aynı işlemi tekrar yapın.
İkisinin toplamını total değerine ekleyin ve bu uzunlukta bir halatı yığına ekleyin.
total değerini döndürün.

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 yığını

Sezgi

Bir min-heap, en kısa ipi kökünde tutar ve kökü çıkarmak ya da bir ip eklemek O(log n) maliyetindedir. Bir tur, size en kısa iki ipi veren iki çıkarma ve birleştirilmiş ipi ekleyen bir ekleme işleminden oluşur.

n ip, her biri üç heap işlemi gerektiren n-1 birleştirme gerektirir; dolayısıyla süre O(n log n) olur: 10^4 ip için yaklaşık 4 × 10^5 adım. Heap hiçbir zaman n ipten fazlasını tutmaz.

Algoritma

Her ip uzunluğunu bir min-yığına koy ve total = 0 olarak ayarla.
Geriye tek bir ip kalana kadar tekrarla: en kısa iki ipi çıkar.
Toplamlarını total değerine ekle ve toplamı yığına geri koy.
total değerini döndür; yalnızca bir ip olduğunda bu değer 0 olarak kalır.

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

Tuzaklar ve uç durumlar

Bir kez sıralayıp her ipi birikimli tek bir ipe eklemek. Birikimli ip, henüz kullanmadığınız iplerden daha uzun hâle gelebilir: [2, 3, 4, 4] için maliyet 5 + 9 + 13 = 27 olurken, en kısa iki ipi birleştirmek 5 + 8 + 13 = 26 tutar.
Birleştirilen ipi yığından çıkarmak. Uzunluğu tekrar yığına eklenir ve sonraki birleştirmede yeniden hesaba katılır.
Son ipin uzunluğunu döndürmek. [5, 2, 8, 3] için son ip 18 uzunluğundadır, ancak maliyet 33'tür.
Yanlışlıkla bir maksimum yığın kullanmak. C++ priority_queue ve Rust BinaryHeap, sıralamayı tersine çevirmediğiniz sürece en büyük değeri verir.

Sıkça sorulan sorular3

Halatların Minimum Maliyetinin zaman karmaşıklığı nedir?

O(n log n) zaman ve O(n) alan kullanımı; bir min-heap ile: n-1 birleştirme, her biri O(log n) olan üç yığın işlemi. Bunun yerine en kısa iki halatı bulmak için tüm yığını taramak, karmaşıklığı O(n²) yapar.

İplerin Minimum Maliyeti, Huffman kodlamasıyla aynı mıdır?

Evet, bu aynı algoritmadır. Huffman kodlaması, en düşük frekansa sahip iki sembolü tekrar tekrar birleştirerek bir önek kodu oluşturur ve her frekansın ağaçtaki derinliğiyle çarpımlarının toplamını en aza indirir. Burada halatlar sembolleri, uzunlukları ise frekansları temsil eder; dolayısıyla toplam maliyet de aynı toplamdır.

Minimum Maliyetli Halatlar problemi yığın kullanılmadan çözülebilir mi?

Evet, iki kuyrukla. Halatları bir kuyruğa göre sırala ve birleştirilen her halatı ikinci kuyruğun sonuna ekle. Birleştirilen halatlar azalmayan sırada çıkar, bu nedenle geriye kalan en kısa halat kuyruklardan birinin başında olur. Böylece her tur O(1) sürer ve uzunluklar en fazla 100 olduğunda sayma sıralaması çalışmayı O(n) yapar.

def minCostRopes(ropes):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

ropes = [5, 2, 8, 3]

Beklenen Çıktı