【題解】ZeroJudge e591: 11264 – Coin Collector

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

  • 【範例】1 3 6 8 15 20
    • 提款 $1 -> {1} (1 種硬幣)
    • 提款 $1 + $3 = $4 -> {1, 3} (2 種硬幣)
    • 提款 $4 + $6 = $10 比 8 大 -> {1, 8} (2 種硬幣)
    • 改成提款 $4 + $8 = $12 -> {1, 3, 8} (3 種硬幣),得到比較多種硬幣
    • 提款 $12 + $15= $27 比 20 大 -> {1, 6, 20} (3 種硬幣)
    • 改成提款 $12 + $20 = $32 -> {1, 3, 8, 20} (4 種硬幣),得到比較多種硬幣
#include <iostream>
using namespace std;

int main() {
    int T, n;
    cin >> T;
    while (T--){
        cin >> n;
        int cur, pre = 0, sum = 0, ans = 0;
        for (int i = 0; i < n; i++){
            cin >> cur;
            if (sum >= cur){
                sum = sum - pre + cur;
            } else {
                sum += cur;
                ans++;
            }
            pre = cur;
        }
        cout << ans << "\n";
    }
    return 0;
}
分享本文 Share with friends