首页 > 试题广场 >

日本旅行

[编程题]日本旅行

热度指数：1168 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

楚乔、宇文玥和燕洵在日本旅行，经过了几天的游玩之后，钱包里出现了大量硬币，楚乔决定用钱包里的硬币为宇文玥和燕洵在自动贩卖机买水。楚乔的钱包里有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

输出

算法知识视频讲解

Java

再向前一点

当硬币问题符合人民币的额度规则，即1、2、5、10这样的规则时，直接使用贪心算法即可，即从大到小进行选择一定为最优解。

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = 6;
        int[] v = new int[]{1,5,10,50,100,500};
        int[] w = new int[n];
        for(int i=0;i<n;i++)
            w[i] = in.nextInt();
        int target = in.nextInt();
        int res = 0;
        for(int i=n-1;i>=0 && target>0;i--){
            for(int j=0;j<w[i] && target>=v[i];j++){
                target-=v[i];
                res++;
            }
        }
        System.out.println(target==0?res:"NOWAY");
    }
}

发表于 2021-08-24 11:03:21 回复(0)