【題目敘述】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;
}