题解：UVA11264 Coin Collector

题目描述

苏丹用钱换硬币，硬币有很多种，苏丹想要换到尽可能多的硬币。规则是：换硬币时优先给你小于等于总金额的面额最大的硬币。

做法

1. 最大的面额必须被选中。
2. 假设 n 是 1 至 i 中那些被选中硬币面额的总和，那么必然存在 n 小于 i-1。

   代码

#include <bits/stdc++.h>
using namespace std;
int a[1005];
int T,n;
int main(){
    cin>>T;
    while(T--){
        int sum=0,s=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<n;i++){
            if(sum<a[i]&&sum+a[i]<a[i+1]){
                sum+=a[i];
                s++;
            }
        }
        cout<<s+1<<endl;
    }
}