排序不同的行

Question

我一直被困在這個問題上。有人可以幫我解決這個問題嗎？

我們給出了長度爲l1，l2，...，ln的n個排序後的行。線條全部按高度排序。我們希望將所有行合併到一個排序行中。我們可以一次合併兩條線，這需要花費兩條線的人數成比例的時間。

設計一種算法，我們可以選擇最佳順序來合併所有行，儘可能少的時間。

Answer 1

考慮貪心算法：

while line number > 1: 
    take the shortest two lines li, lj 
    merge them 

這是最佳的解決方案？您將看到以下事實屬實：

• 如果你知道合併樹（也就是它告訴你的樹，其對線的合併，當（更深的元素被合併第一和樹從讀從左到右））我們可以看到，一個最佳解決方案就是這個長度較短的線條具有較大深度的線條。我們可以從樹上開始填充樹，從下到上，行長按升序排序。
• 這意味着最小的兩行是在葉子
• 改變葉子順序不會改變最優解
• 我們可以重新排序最小的線是前兩個葉子 因此，我們已經找到了最佳的解決方案我們挑選合併兩條最短長度的線。通過歸納，我們可以繼續這樣。

您可以使用最小優先級隊列實現此算法。

initialize min-priority queue q  
insert all line lengths in q 
ans = 0 
while q > 1: 
    a = q.pop() 
    b = q.pop() 
    ans += a+b 
    q.push(a+b) 
return ans