首页 > 试题广场 >

硬币兑换

[编程题]硬币兑换

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

A 国一共发行了几种不同面值的硬币，分别是面值 1 元，2 元，5 元，10 元，20 元，50 元， 100 元。假设每种面值的硬币数量是无限的，现在你想用这些硬币凑出总面值为 n 的硬币，同时你想让选出的硬币中，不同的面值种类尽可能多;在面值种类尽可能多的情况下，你想让选择的硬币总数目尽可能多，请问应该怎么选择硬币呢?

数据范围： $1 \le n \le 10^9 \$

输入描述:

第一行包含一个数字𝑛，表示要凑出的面值。

输出描述:

输出两个整数，分别表示最多能有多少种类型的硬币以及在类型最多的情况下最多能用上多少枚硬币。

示例1

输入

输出

2 2

示例2

输入

输出

3 5

算法知识视频讲解

Java

洋葱入侵

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);

        while(sc.hasNext()){
            int n = sc.nextInt();
            int[] res = getCoins(n);
            System.out.println(res[0] + " " + res[1]);
        }

    }
    
    // 贪心，从面值1 开始一个一个加面值种类，加到最后如果还有剩的，全部换成面值1的硬币
    public static int[] getCoins(int n){
        // res[0] : 种类数， res[1]：硬币数
        int[] res = new int[2];
        if (n - 1 >= 0){
            n = n - 1;
            res[0]++;
            res[1]++;
        }
        if (n - 2 >= 0){
            n = n - 2;
            res[0]++;
            res[1]++;
        }
        if (n - 5 >= 0){
            n = n-5;
            res[0]++;
            res[1]++;
        }
        if (n - 10 >= 0){
            n = n - 10;
            res[0]++;
            res[1]++;
        }
        if (n - 20 >= 0){
            n = n - 20;
            res[0]++;
            res[1]++;
        }

        if (n - 50 >= 0){
            n = n - 50;
            res[0]++;
            res[1]++;
        }

        if (n - 100 >= 0){
            n = n - 100;
            res[0]++;
            res[1]++;
        }

        res[1] += n;

        return res;
    }
}

发表于 2022-03-16 03:19:47 回复(0)

Java

Mono_Chrome

import java.util.Scanner;

public class Main {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[]{1, 2, 5, 10, 20, 50, 100};
        int[] sum = new int[8];
        for (int i = 1; i < 8; i++) {
            sum[i] = sum[i - 1] + arr[i - 1];
        }
        for (int i = sum.length - 1; i > 0; i--) {
            if (n >= sum[i]) {
                System.out.println(i + " " + (n - sum[i] + i));
                break;
            }
        }
    }
}

发表于 2019-06-16 14:56:18 回复(0)