首页 > 试题广场 >

硬币兑换

[编程题]硬币兑换

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

输出

2 2

示例2

输入

输出

3 5

算法知识视频讲解

wylu

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)

pein531

贪心，先保证硬币种类尽可能多，按照面值从小到大凑（因为要慢慢凑，先用小面额）。如果硬币种类满了还没凑够，就用1元来接着凑，保证硬币数多；如果再加上个大额硬币会超过目标值，也采用1元硬币来接着凑，保证硬币数多。

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] coin = new int[]{1, 2, 5, 10, 20, 50, 100};
        int n = Integer.parseInt(br.readLine().trim());
        int type = 0, count = 0, sum = 0;
        for(int i = 0; i < coin.length; i++){
            // 按面值升序遍历每种硬币，先保证硬币种类尽可能多
            if(sum + coin[i] <= n){
                sum += coin[i];
                count ++;
                type ++;
            }else
                break;
        }
        if(sum < n) count += n - sum;     // 不够的用1元硬币来凑，保证硬币数尽可能多
        System.out.println(type + " " + count);
    }
}

发表于 2021-04-06 10:51:03 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, x=0, y=0, a[8] = {0, 1, 2, 5, 10, 20, 50, 100}, s[8]={0};
    scanf("%d", &n);
    for(int i=1;i<8;i++){
        s[i] = s[i-1] + a[i];
        if(s[i]<=n){
            x = i;
            y = n - s[i] + i;
        }
    }
    printf("%d %d\n", x, y);
    return 0;
}

发表于 2020-09-17 00:53:40 回复(0)

ID84848484

//依次计算出前 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)

cnalong


	/*
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)

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)

Shelven丶

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int z;
	cin >> z;
	int zz = z, i = 0, j = 0;
	vector<int> vi{ 1,2,5,10,20,50,100 };
	while (z >= vi[i])
	{
		j += vi[i];
		z -= vi[i++];
		if (i == 7)break;
	}
	cout << i << " " << i + zz - j;
}

发表于 2020-04-13 13:52:40 回复(0)

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)

C/C++

牛客549207409号

#include<iostream>
int main()
{
long long n;
while(std::cin>>n)
{
if(n==1)std::cout<<1<<" "<<1<<std::endl;
else if(n==2)std::cout<<1<<" "<<2<<std::endl;
else if(n<8)std::cout<<2<<" "<<n-1<<std::endl;
else if(n<18)std::cout<<3<<" "<<n-5<<std::endl;
else if(n<38)std::cout<<4<<" "<<n-14<<std::endl;
else if(n<88)std::cout<<5<<" "<<n-33<<std::endl;
else if(n<188)std::cout<<6<<" "<<n-82<<std::endl;
else std::cout<<7<<" "<<n-181<<std::endl;
}
return 0;
}

发表于 2020-09-13 18:17:54 回复(0)

.晚安

n = int(input())
l = [i for i in [1, 3, 8, 18, 38, 88, 188] if i <= n]
print(len(l), len(l) + n - l[-1])

发表于 2020-07-16 15:45:30 回复(0)

南神201909010856681

#include<iostream>
using namespace std;
int main()
{
    int N;
    cin>>N;
    if(N==1) cout<<1<<' '<<1;
    else if(N==2) cout<<1<<' '<<2;
    else if(N>=3&&N<8) cout<<2<<' '<<N-3+2;
    else if(N>=8&&N<18) cout<<3<<' '<<N-8+3;
    else if(N>=18&&N<38) cout<<4<<' '<<N-18+4;
    else if(N>=38&&N<88) cout<<5<<' '<<N-38+5;
    else if(N>=88&&N<188) cout<<6<<' '<<N-88+6;
    else cout<<7<<' '<<N-188+7<<endl;
}

发表于 2019-09-10 21:48:49 回复(0)

hzpzlz1314

#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)