Minimum Cost of Ropes

Q: Độ phức tạp thời gian của MinCostRopes là bao nhiêu?

Độ phức tạp thời gian O(n log n) và bộ nhớ O(n) với đống tối thiểu (min-heap): n-1 lần nối, mỗi lần gồm ba thao tác trên đống, mỗi thao tác có độ phức tạp O(log n) . Thay vào đó, nếu duyệt toàn bộ đống dây để tìm hai sợi dây ngắn nhất thì độ phức tạp sẽ là O(n²) .

DễHeap Tham lam

+10

Bạn có một số sợi dây, trong đó ropes[i] là độ dài của sợi dây i. Bạn có thể nối hai sợi dây bất kỳ thành một sợi dây có độ dài bằng tổng độ dài của chúng, và chi phí nối cũng bằng tổng đó. Bạn tiếp tục nối cho đến khi chỉ còn một sợi dây.

Viết một hàm có tên minCostRopes trả về tổng chi phí nhỏ nhất để nối tất cả các sợi dây thành một sợi, hoặc 0 nếu ban đầu chỉ có một sợi dây.

Hàm

minCostRopes(ropes: integer-array) → integer

ropesinteger-array: độ dài của mỗi sợi dây
Trả vềinteger: tổng chi phí nhỏ nhất để nối tất cả các sợi dây thành một

Ràng buộc

1 ≤ ropes.length ≤ 10⁴
1 ≤ ropes[i] ≤ 100
Đáp án nằm trong phạm vi số nguyên có dấu 32 bit.

Ví dụ

Đầu vào: ropes = [5, 2, 8, 3]
Đầu ra: 33
Giải thích: Gộp 2 và 3 thành 5, hai sợi dây có độ dài 5 thành 10, rồi gộp 8 và 10 thành 18. Tổng cộng là 5 + 10 + 18 = 33.

Đầu vào: ropes = [1, 1, 1, 1]
Đầu ra: 8
Giải thích: Ghép các sợi dây có độ dài 1 thành từng cặp, mỗi cặp tốn 2, rồi ghép hai sợi dây có độ dài 2 với chi phí 4: tổng cộng là 8. Nếu thêm từng sợi dây có độ dài 1 vào một sợi dây đang dài dần, chi phí sẽ là 2 + 3 + 4 = 9.

Câu hỏi mở rộng

Giả sử một mối nối có thể ghép tối đa ba sợi dây và chi phí bằng tổng chiều dài của chúng. Quy tắc tham lam thay đổi thế nào khi số lượng dây không chia hết cho ba?

Lời giải

Mỗi lần nối đều tính toàn bộ độ dài của cả hai đoạn, nên một sợi dây đã nối từ sớm sẽ lại được tính trong mỗi lần nối sau có sợi dây đó. Tránh nối những sợi dây dài từ sớm: hãy nối hai sợi dây ngắn nhất ở mỗi lượt. Min-heap tìm ra hai sợi dây đó trong O(log n).

Hãy quét tìm hai sợi dây ngắn nhất ở mỗi lượt

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Mỗi vòng, hãy tìm sợi dây ngắn nhất trong đống rồi lấy ra, tìm lại để chọn sợi dây ngắn thứ hai, sau đó đặt mối nối của chúng trở lại.

Tại sao lại chọn hai sợi ngắn nhất: hãy vẽ các mối nối thành một cây, trong đó các sợi dây là lá. Chiều dài của một sợi dây được tính một lần cho mỗi mối nối phía trên nó, tức là theo độ sâu của nó. Ở tầng sâu nhất có hai lá nằm cạnh nhau, và đưa hai sợi dây ngắn nhất đến đó không bao giờ làm tăng chi phí. Vì vậy, có một phương án tối ưu nối hai sợi dây ngắn nhất trước, rồi lập luận này lặp lại với đống nhỏ hơn.

Có n-1 vòng, mỗi vòng gồm hai lượt quét toàn bộ: O(n²), khoảng 10^8 phép so sánh với 10^4 sợi dây.

Thuật toán

Sao chép các sợi dây vào danh sách làm việc pile và đặt total bằng 0.
Lặp lại cho đến khi còn một sợi dây: tìm sợi dây ngắn nhất rồi xóa nó bằng cách chuyển sợi dây cuối cùng vào vị trí của nó.
Làm tương tự để tìm sợi dây ngắn thứ hai.
Cộng độ dài của hai sợi dây vào total rồi thêm một sợi dây có độ dài đó vào danh sách.
Trả về 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

Ý tưởng

Min-heap giữ sợi dây ngắn nhất ở gốc, còn việc lấy gốc ra hoặc chèn một sợi dây có chi phí O(log n). Mỗi lượt gồm hai lần lấy ra, đưa cho bạn hai sợi dây ngắn nhất, và một lần chèn sợi dây đã nối.

n sợi dây cần n-1 lần nối, mỗi lần gồm ba thao tác trên heap, nên độ phức tạp thời gian là O(n log n): khoảng 4 × 10^5 bước với 10^4 sợi dây. Heap không bao giờ chứa quá n sợi dây.

Thuật toán

Đưa độ dài của từng sợi dây vào một đống tối thiểu và đặt total = 0.
Lặp lại cho đến khi chỉ còn một sợi dây: lấy ra hai sợi ngắn nhất.
Cộng tổng độ dài của chúng vào total rồi đẩy tổng đó trở lại đống.
Trả về total, giá trị này vẫn là 0 nếu ban đầu chỉ có một sợi dây.

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

Lỗi thường gặp và trường hợp biên

Sắp xếp một lần rồi lần lượt nối từng sợi dây vào một sợi dây đang dài dần. Sợi dây đang nối có thể dài hơn những sợi dây bạn chưa dùng: với [2, 3, 4, 4], chi phí là 5 + 9 + 13 = 27, trong khi nối hai sợi ngắn nhất có chi phí là 5 + 8 + 13 = 26.
Bỏ sợi dây đã nối ra. Độ dài của nó quay lại đống dây và được tính phí lần nữa khi nối sau đó.
Trả về độ dài của sợi dây cuối cùng. Với [5, 2, 8, 3], sợi dây cuối cùng dài 18, nhưng chi phí là 33.
Vô tình dùng max-heap. priority_queue của C++ và BinaryHeap của Rust sẽ lấy ra giá trị lớn nhất, trừ khi bạn đảo ngược thứ tự.

Câu hỏi thường gặp3

Độ phức tạp thời gian của MinCostRopes là bao nhiêu?

Độ phức tạp thời gian O(n log n) và bộ nhớ O(n) với đống tối thiểu (min-heap): n-1 lần nối, mỗi lần gồm ba thao tác trên đống, mỗi thao tác có độ phức tạp O(log n). Thay vào đó, nếu duyệt toàn bộ đống dây để tìm hai sợi dây ngắn nhất thì độ phức tạp sẽ là O(n²).

Chi phí tối thiểu để nối dây có giống với mã hóa Huffman không?

Đúng vậy, đây là cùng một thuật toán. Mã hóa Huffman tạo mã tiền tố bằng cách liên tục ghép hai ký hiệu có tần suất thấp nhất, đồng thời giảm thiểu tổng của mỗi tần suất nhân với độ sâu của ký hiệu đó trong cây. Ở đây, các sợi dây đóng vai trò là các ký hiệu, còn độ dài của chúng đóng vai trò là tần suất, nên tổng chi phí chính là tổng đó.

Có thể giải bài toán MinCostRopes mà không cần heap không?

Đúng vậy, với hai hàng đợi. Sắp xếp các sợi dây vào một hàng đợi rồi đưa mỗi sợi dây đã nối vào cuối hàng đợi thứ hai. Các sợi dây đã nối được lấy ra theo thứ tự không giảm, nên sợi dây ngắn nhất còn lại nằm ở đầu một trong hai hàng đợi. Khi đó, mỗi lượt mất O(1), và với độ dài tối đa là 100, thuật toán sắp xếp đếm giúp thời gian chạy là O(n).

def minCostRopes(ropes):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

ropes = [5, 2, 8, 3]

Đầu ra mong đợi