Uva11264 - Coin Collector

題目大意

題目給與所有的硬幣面額，我們需要找出從銀行取得錢時最多可以拿幾種硬幣(銀行會從大的面額開始給)

重點觀念

• 沒

分析

• 依直覺，若遇到面額比所有目前選取錢幣加起來還大，則直接選取
• 否則取消選取上一個你選取的錢幣並選取此前幣

程式題目碼

#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        int cur, pre = 0, sum = 0, count = 0;

        for (int i = 0; i < n; i++) {
            cin >> cur;

            if (sum < cur) {
                sum += cur;
                count++;
            } else {
                sum = sum - pre + cur;
            }

            pre = cur;
        }

        cout << count << endl;
    }

    return 0;
}