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

输入描述:
第一行包含一个数字𝑛,表示要凑出的面值。1 ≤ 𝑛 ≤ 109


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

输入

3

输出

2 2
示例2

输入

10

输出

3 5
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        int[] coin = {0, 1, 2, 5, 10, 20, 50, 100};
        int[] sum = new int[8];
        for (int i = 1; i < coin.length; i++) {
            sum[i] += sum[i - 1] + coin[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-03-13 14:09:00 回复(0)
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)
//依次计算出前  x 种面值的和,x<=7
//从大到小找到比n小的第一个面值和
//最多不同面值则为其下标
//剩下的用面值1去填

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[] money={1,2,5,10,20,50,100};
        int[] sum={1,3,8,18,38,88,188};
        int dif=1;
        int count=1;
        int index=0;
        for(int i=6;i>=0;i--){
            if(n>=sum[i])
            {
                index=i;
                break;
            }
        }
        dif=index+1;
        count=dif+n-sum[index];
        System.out.println(dif+" "+count);
    }
}

发表于 2019-04-25 22:06:58 回复(0)
/* A 国一共发行了几种不同面值的硬币,分别是面值 1 元,2 元,5 元,10 元,20 元,50 元, 100 元。假设每种面值的硬币数量是无限的,现在你想用这些硬币凑出总面值为 n 的硬币, 同时你想让选出的硬币中,不同的面值种类尽可能多;在面值种类尽可能多的情况下,你想 让选择的硬币总数目尽可能多,请问应该怎么选择硬币呢? */
import java.util.Scanner; public class Q3 {     public static void main(String[] args)     {         Scanner sc = new Scanner(System.in);         long value = sc.nextLong();         if(value>=188)         {             System.out.print(7+" ");             System.out.println(value-181);         }         else if(value>=88)         {             System.out.print(6+" ");             System.out.println(value-82);         }         else if(value>=38)         {             System.out.print(5+" ");             System.out.println(value-33);         }         else if(value>=18)         {             System.out.print(4+" ");             System.out.println(value-14);         }         else if(value>=8)         {             System.out.print(3+" ");             System.out.println(value-5);         }         else if(value>=3)         {             System.out.print(2+" ");             System.out.println(value-1);         }         else         {             System.out.print(1+" ");             System.out.println(value);         }     } }

发表于 2019-02-18 12:53:17 回复(0)

这题 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)
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int money[7]={1,2,5,10,20,50,100};
    int n;
    cin>>n;
    vector<int>sums(8);
    for(int i=0;i<7;i++){
        sums[i+1]=sums[i]+money[i];
    }
    int num;
    int res;
    if(sums[7]<n){
        int sy = n-sums[7];
        cout<<7<<" "<<7+sy<<endl;
    }
    else{
        for(int i=1;i<8;i++){
            if(sums[i]==n){
                num=i;
                res = 0;
                break;
            }
            if(sums[i]>n){
                num = i-1;
                res=n - sums[i-1];
                break;
            }
        }
        cout<<num<<" "<<num+res<<endl;
    }
    return 0;
}
//题不难,贡献cpp
发表于 2019-04-12 20:15:10 回复(0)
n=int(input()) if(n==1): print(1,1) elif(n<3): print('1',2) elif(n<8): print('2',n-1) elif(n<18): print('3',n-5) elif(n<38): print('4',n-14) elif(n<88): print('5',n-34) elif(n<188): print('6',n-82) else: print('7',n-181)


发表于 2019-03-26 20:12:44 回复(0)