首页 > 试题广场 > 硬币兑换
[编程题]硬币兑换
A 国一共发行了几种不同面值的硬币,分别是面值 1 元,2 元,5 元,10 元,20 元,50 元, 100 元。假设每种面值的硬币数量是无限的,现在你想用这些硬币凑出总面值为 n 的硬币, 同时你想让选出的硬币中,不同的面值种类尽可能多;在面值种类尽可能多的情况下,你想 让选择的硬币总数目尽可能多,请问应该怎么选择硬币呢?
输入描述:
第一行包含一个数字𝑛,表示要凑出的面值。1 ≤ 𝑛 ≤ 109


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

输入

3

输出

2 2
示例2

输入

10

输出

3 5

1个回答

添加回答

这题 case有问题

9999999999
7 1410065226

这个case是错误的,然后用如下代码能ac。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long[] coins = new long[] {1, 2, 5, 10, 20, 50, 100};
        long[] preSum = new long[9];
        for (int i=1; i!=8; i++) {
            preSum[i] = coins[i-1] + preSum[i-1];
        }
        preSum[8] = Long.MAX_VALUE;
        long lin = sc.nextLong();
        int in = (int) lin;
        int i = 0;
        for (i=1; i!=8; i++) {
            if (preSum[i] > in) {
                break;
            }
        }
        System.out.printf("%d %d\n", i-1, in - preSum[i-1] + i-1);
    }
}
但正确的代码是
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long[] coins = new long[] {1, 2, 5, 10, 20, 50, 100};
        long[] preSum = new long[9];
        for (int i=1; i!=8; i++) {
            preSum[i] = coins[i-1] + preSum[i-1];
        }
        preSum[8] = Long.MAX_VALUE;
        long in = sc.nextLong();
        int i = 0;
        for (i=1; i!=8; i++) {
            if (preSum[i] > in) {
                break;
            }
        }
        System.out.printf("%d %d\n", i-1, in - preSum[i-1] + i-1);
    }
}
发表于 2019-02-10 19:50:03 回复(0)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号