【题目】
楚乔、宇文玥和燕洵在日本旅行,经过了几天的游玩之后,钱包里出现了大量硬币,楚乔决定用钱包里的硬币为宇文玥和燕洵在自动贩卖机买水。楚乔的钱包里有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
【思路】
从大面值往小面值取 贪心即可
【实现】
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Scanner;public class Main{public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] tmp = br.readLine().split(" ");br.close();int[] values = {1,5,10,50,100,500};int[] amount = {0,0,0,0,0,0};for(int i = 0;i<6;i++){amount[i] = Integer.parseInt(tmp[i]);}int res = 0;int A = Integer.parseInt(tmp[6]);for(int i = 5;i>=0;i--){if(A>values[i]){int t = A/values[i];if(amount[i] < t){t = amount[i];}res += t;A-= t*values[i];}}if(A==0) System.out.println(res);else System.out.println("NOWAY");}}