贪心找零钱

题目描述

楚乔、宇文玥和燕洵在日本旅行，经过了几天的游玩之后，钱包里出现了大量硬币，楚乔决定用钱包里的硬币为宇文玥和燕洵在自动贩卖机买水。楚乔的钱包里有1元、5元、10元、50元、100元和500元硬币各C1,C5,C10,C50,C100,C500枚。现在要用这些硬币来到自动贩卖机买价格为A的饮料，假设自动贩卖机所需的硬币金额必须是刚刚好，不能多也不能少，最少需要多少枚硬币？

限制条件

0≤ C1,C5,C10,C50,C100,C500≤1000000000

0≤A≤1000000000

依次输入C1,C5,C10,C50,C100,C500和A，以空格分隔，输出最少所需硬币数，如果该金额不能由所给硬币凑出，则返回NOWAY

输入描述:

依次输入C1,C5,C10,C50,C100,C500和A，以空格分隔

输出描述:

输出最少所需硬币数，如果该金额不能由所给硬币凑出，则返回NOWAY

示例1

输入

复制

3 2 1 3 0 2 620

输出

复制

6

说明

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

bool Cmp(const pair<int,int>& A,const pair<int,int>& B){
    return A.first > B.first;
}

int main(){
    vector<pair<int,int>> Vec;int Result = 0;
    int C1,C5,C10,C50,C100,C500,A;
    cin >> C1 >>C5 >> C10 >>C50 >>C100 >>C500 >> A;
    Vec.push_back(make_pair(1,C1));
    Vec.push_back(make_pair(5,C5));
    Vec.push_back(make_pair(10,C10));
    Vec.push_back(make_pair(50,C50));
    Vec.push_back(make_pair(100,C100));
    Vec.push_back(make_pair(500,C500));
    sort(Vec.begin(),Vec.end(),Cmp);
    for(int i = 0;i < 6;i ++){
        int Need = A / Vec[i].first;
        if(Need <= Vec[i].second){
            A = A - Need * Vec[i].first;
            Result += Need;
        }
        else {
            A = A - Vec[i].first * Vec[i].second;
            Result += Vec[i].second;
        }
    }
    if(A > 0){
        cout << "NOWAY" << endl;
    }
    else {
        cout << Result << endl;
    }
    return 0;
}