【題解】ZeroJudge d221: 10954 – Add All

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d221
【解題想法】Greedy【筆記

  • 因為加法的代價會不斷累計,因此不斷地從最小的數字先相加,代價最低。
  • 利用priority_queue,但排序由小到大。取出最小的兩個數字,相加後放回priority_queue,重新排序。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n, num, a, b;
    while (cin >> n){
        if (n == 0) break;
        priority_queue <int, vector<int>, greater<int>> pq;
        long long count = 0;
        for (int i = 0; i < n; i++){
            cin >> num;
            pq.push(num);
        }
        for (int i = 0; i < n-1; i++){
            a = pq.top();
            pq.pop();
            b = pq.top();
            pq.pop();
            count += a+b;
            pq.push(a+b);
        }
        cout << count << endl;
    }
}

while True:
    try:
        n = int(input())
        if n == 0:
            break
        lst = list(map(int, input().split()))
        lst.sort()
        ans = 0
        total = lst[0]
        for i in range(n-1):
            num = lst.pop(0) + lst.pop(0)
            ans += num
            lst.append(num)
            lst.sort()
        print(ans)
    except:
        break
分享本文 Share with friends