日本旅行

题目链接

贪心法

由于钱之间存在因子关系，所以可以贪。
这种方法时最直观的，也是最容易想到的。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int INF = 0x3fffffff;
int m,n; 
int main(){
    int c1,c5,c10,c50,c100,c500,A;
    while(cin>>c1>>c5>>c10>>c50>>c100>>c500>>A){
        int cnt=0;
        while(A >= 500 && c500 > 0){
            A -= 500;
            c500--;
            cnt++;
        }
        while(A >= 100 && c100 > 0){
            A -= 100;
            c100--;
            cnt++;
        }
        while(A >= 50 && c50 > 0){
            A -= 50;
            c50--;
            cnt++;
        }
        while(A >= 10 && c10 > 0){
            A -= 10;
            c10--;
            cnt++;
        }
        while(A >= 5 && c5 > 0){
            A -= 5;
            c5--;
            cnt++;
        }
        while(A >= 1 && c1 > 0){
            A -= 1;
            c1--;
            cnt++;
        }
        if(A == 0) cout<<cnt<<endl;
        else cout<<"NOWAY"<<endl; 
    }
    return 0;
}