ZeroJudge 解題筆記：d221. 10954 - Add All

作者：王一哲
日期：2026年5月4日


ZeroJudge 題目連結：d221. 10954 - Add All

解題想法

用最小優先佇列 pq 儲存數字，每次取出其中最小的兩個數字 a、b，a、b 相加為 c，更新成本 cost 之後再將 c 存回 pq，直到 pq 之中只剩下一個數字為止。如果用 C++ 解題要用 long long 儲存答案，用 int 會溢位。

Python 程式碼

使用時間約為 99 ms，記憶體約為 13.6 MB，通過測試。

def solve():
    import sys, heapq

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if n == 0: break
        pq = []
        for _ in range(n):
            x = int(data[ptr])
            ptr += 1
            heapq.heappush(pq, x)
        
        cost = 0
        while len(pq) >= 2:
            a = heapq.heappop(pq)
            b = heapq.heappop(pq)
            c = a + b
            cost += c
            heapq.heappush(pq, c)
        result.append(f"{cost:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 11 ms，記憶體約為 3.1 MB，通過測試。

#include <cstdio>
#include <queue>
#include <functional>
typedef unsigned long long LL;
using namespace std;

int main() {
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {
        priority_queue<LL, vector<LL>, greater<LL>> pq;
        for(int i=0; i<n; i++) {
            LL v; scanf("%llu", &v);
            pq.push(v);
        }
        LL cost = 0;
        while(pq.size() >= 2) {
            LL a = pq.top(); pq.pop();
            LL b = pq.top(); pq.pop();
            LL c = a + b;
            cost += c;
            pq.push(c);
        }
        printf("%llu\n", cost);
    }
    return 0;
}