UVa10954 - Add All(水題)

題目大意

給你一個數列，請善用 a+b=c, cost += c ，其中 a 與 b 是數列裡面的數字，並將 c 再放入數列
請求出最小的 cost

題目連結

重點觀念

• priority_queue 的應用
  priority_queue 是 heap sort 的應用，理論就是不斷拿出 heap tree 的 root，需要看 heap sort 請看大衞的筆記

分析

• 我們可以知道不斷拿數列中兩個最小的數字相加會使得 cost 最小
  如果你覺得不可信，可以看看題目舉例
• 因此我們使用 priority_queue 每次取出兩個最小的相加即可。

心得

水題，給我自信XD。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN
#define int long long
using namespace std;
int n, num;
//注意，這是最小遞增 priority_queue 的寫法
priority_queue<int, vector<int>, greater<int> > q; 

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL


    while(cin >> n && n){
        while(!q.empty()) q.pop(); //clear, priority_queue 沒有 clear 的 method  

        for(int i = 0; i < n; i++){  //輸入資料
            cin >> num;
            q.push(num);
        }

        int ans = 0, a, b;
        while(q.size() != 1){ //只要數列中還有兩個以上的數字可以累加
            a = q.top(); q.pop();
            b = q.top(); q.pop();
            q.push(a+b);
            ans += a+b;
        }
        cout << ans << '\n';

    }

    return 0;
}