tags: APCS

d221－Add All

題目連結： d221

題目解析

這道題目要求我們將一系列的數字加起來，但每次加法操作的代價是兩個數字的總和。目標是使總加法代價最小化。這是一個經典的貪心算法問題，通常使用最小堆積（Min Heap）來解決，但此題用的是類似的方法。

解題方向

為了讓總加法代價最小，我們每次都應該選擇兩個最小的數字進行加法，這樣才能減少累積的代價。因此，我們首先對數字進行排序，並從最小的兩個開始加，每次計算新值後，再將其插入排序好的列表中，重複這個過程直到列表中只剩下一個元素。

程式解析

1. 初始化輸入資料：我們首先讀入數字 N，表示數字的個數，並進行檢查，如果 N 為 0，則結束輸入。
2. 排序列表：接下來，我們讀入所有數字並對其進行排序，使數字按從小到大的順序排列。這樣，我們每次可以很方便地取出最小的兩個數字。
3. 進行加法操作：使用 for 迴圈執行 N-1 次操作。每次都從列表中取出兩個最小的數字，將它們相加並將其結果加入到總代價中。然後，將這個結果插入回列表並再次排序。
4. 輸出結果：最後，當只剩下一個元素時，已經計算完所有的加法代價，並將結果輸出。

完整程式碼

while True:
    try:
        N = int(input())
        if N == 0:
            break
        num = list(map(int, input().split()))
        num.sort() # 將所有數字排序為由小到大

        ans = 0

        for i in range(N-1):
            a = num.pop(0) # 移除並返回最小的元素
            b = num.pop(0) # 移除並返回次小的元素
            # 拉出最小的兩個值
            c = a + b # 將兩個最小的數字相加
            ans += c # 將此次加法操作的代價累加到總代價中
            num.append(c) # 把新加出的值插回數字列表中
            num.sort() # 重新排序，保證最小值總是在列表最前端

        print(ans) # 輸出結果

    except:
        break