首页 > 试题广场 >

找零

[编程题]找零

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

Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为 $N (0 < N \le 1024)$ 的商品，请问最少他会收到多少硬币？

输入描述:

一行，包含一个数N。

输出描述:

一行，包含一个数，表示最少收到的硬币数。

示例1

输入

输出

说明

花200，需要找零824块，找12个64元硬币，3个16元硬币，2个4元硬币即可。

备注:

对于100%的数据，。

算法知识视频讲解

Java

青春猪头少年不会没有offer

完全背包问题。

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = 1024 - in.nextInt();
        int[] g = {1, 4, 16, 64};
        int[] dp = new int[t + 1];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;
        for (int gg: g) {
            for (int j = gg; j <= t; ++j) {
                dp[j] = Math.min(dp[j], dp[j - gg] + 1);
            }
        }
        System.out.println(dp[t]);
    }
}

发表于 2023-12-21 10:33:38 回复(0)

Java

runningrookies

//来提供点有趣的思路，用位运算
public class Main { public static void main(String[] args){
        Scanner sc = new Scanner(System.in);  int n = sc.nextInt();  n = 1024 - n;  int ans = 0;  int k = 3;  while (k-- > 0) { int temp = n & 3;  ans +=temp;  n = n>>2;  }
        ans += n;  System.out.println(ans);  }
}

发表于 2022-01-23 14:01:12 回复(0)

Java

牛客777252312号

发表于 2021-10-01 18:08:45 回复(0)

Java

石秀官

import java.util.Scanner; //java.util为包名，Scanner为类名

public class Main
{
	public static void main(String[] args) // 切莫少了传入参数
	{
		Scanner input = new Scanner( System.in ); //使用前先导入Scanner类
        int N = input.nextInt(); //next() 为方法
        input.close();
        int Z = 1024-N;
        int n64 = Z/64;
        int S = Z-64*n64; // *不能少，和数学里的带分数的单项式不同
        int n16 = S/16;
        S = S-16*n16; //切莫重复定义，应用之前剩下的来减
        int n4 = S/4;
        S = S-4*n4;
        int NS = n64+n16+n4+S;
        System.out.println( NS ); //输出语句切莫和C语言搞混
	}
}

发表于 2020-12-29 20:15:06 回复(0)

Java

逸非凡

public static void main(String[] args) throws IOException {
      Scanner s=new Scanner(System.in);
        Integer n=s.nextInt();
        Integer  money=s.nextInt();
        int  balance=n-money;

       int a=balance/64;

       int b=balance%64/16;

        int c= balance%64%16/4;

        int d=balance%64%16%4/1;

        System.out.println(a+b+c+d);
      
    }

这代码我在idea里运行成功，提交就报错，我提交9次还是报错，大家看看有什么问题

发表于 2020-09-05 09:57:05 回复(1)

Java

hhhhh.

繁琐

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n;
        n = scanner.nextInt();
        int zhaoling = 1024 - n;
        int x = 0,y = 0,z = 0,m = 0;//x-1yuan,y-4yuan,z-16yuan,m-64yuan
        m = zhaoling / 64;
        if(zhaoling % 64 != 0){
            zhaoling = zhaoling - m * 64;
            z = zhaoling / 16;
            if(zhaoling %16 != 0){
                zhaoling = zhaoling - z * 16;
                y = zhaoling / 4;
                if(zhaoling % 4 != 0){
                    zhaoling = zhaoling - y * 4;
                    x = zhaoling;
                }
                
            }
        }
        int sum = x + y + z + m;
        System.out.println(sum);
    }
}

发表于 2020-07-31 23:29:22 回复(0)

Java

工大月

import java.util.Scanner;

public class Main {

	public static void printCoinNum(int price){
		//过滤到非法的商品price
		if(price <=0 || price > 1024){
			return;
		}
		int num = 1024 - price; //应该找回的零钱
    	int count1 = num / 64; //64元硬币的数量
    	int temp1 = num - (count1*64);
    	int count2 = temp1 / 16; //16元硬币的数量
    	int temp2 = temp1 - (count2*16);
    	int count3 = temp2 / 4; //4元硬币的数量
    	int temp3 = temp2 - (count3*4);
    	int count4 = temp3 / 1; //1元硬币的数量
    	int temp4 = temp3 - (count4*1);
    	
    	if(temp4 ==0){
    		System.out.println(count1 + count2 + count3 + count4); //应找零钱的硬币总数
    	}else{
    		System.out.println("error!");
    	}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int price = sc.nextInt();
			printCoinNum(price);
		}
		sc.close();
	}

}

发表于 2020-07-27 20:48:33 回复(0)

Java

小陈也只是想要一个实习罢了

import java.util.Scanner;

public class Main {
    public static int minCoins(int give){
        int remain=1024-give,cnt=0;
        while(remain!=0){
            if(remain>=64){
                cnt+=remain/64;
                remain-=remain/64*64;
            }else if(remain>=16){
                cnt+=remain/16;
                remain-=remain/16*16;
            }else if(remain>=4){
                cnt+=remain/4;
                remain-=remain/4*4;
            }else{
                cnt+=remain;
                remain=0;
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int input=scanner.nextInt();
        System.out.println(Main.minCoins(input));
    }
}

发表于 2020-06-05 19:54:18 回复(0)

Java

何止hz

//动态规划
import java.util.Scanner;

/**
 * @Date: 2020-05-06 22:13
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = 1024 - sc.nextInt();
        int dp[] = new int[t+1];
        for (int i = 1; i <= t; i++){
            dp[i] = dp[i-1];
            if (i - 4 >= 0){
                dp[i] = Math.min(dp[i], dp[i-4]);
                if (i - 16 >= 0){
                    dp[i] = Math.min(dp[i], dp[i-16]);
                    if (i - 64 >= 0)
                        dp[i] = Math.min(dp[i], dp[i-64]);
                }
            }
            dp[i]++;
        }
        System.out.println(dp[t]);
    }
}

发表于 2020-05-06 22:22:31 回复(0)

Java

Nakangzi

老老实实动态规划，要注意的是此处应该是1024减去商品价格才是要找的钱的总额

import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = 1024-sc.nextInt();
            int[]coins={1,4,16,64};
            int max=n+1;
            int[]dp=new int[max+1];
            Arrays.fill(dp,max);
            dp[0]=0;
            for(int i=1;i<=n;i++){
                for(int coin:coins){
                    if(i>=coin)dp[i]=Math.min(dp[i],dp[i-coin]+1);
                }
            }
            System.out.println(dp[n]);
        }
    }
}

发表于 2020-03-07 17:20:00 回复(1)

Java

LHC0512

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);  int i = scanner.nextInt();  i= 1024-i;  int sum = i/64;  i=i%64;  if (i>0){
        sum+=i/16;  i=i%16;  if (i>0){
            sum+=i/4;  i=i%4;  if (i>0){
                System.out.println(sum+i);  return;  }
        }
    }
    System.out.println(sum); }

发表于 2020-02-28 20:33:01 回复(0)

Java

只是而已

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner sc =new Scanner(System.in);

int n =1024-sc.nextInt();

int sum =0;

int count =64;

while (count>=1){

if (n%count==0){

sum+=n/count;

break;

}else {

sum+=n/count;

n=n%count;

count=count/4;

}

System.out.println(sum);

}

编辑于 2019-09-20 01:13:23 回复(0)

Java

1+½+¼+⅛+...

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        input.close();
        System.out.println(Solution(N));
    }
    
    public static int Solution(int N) {
    	return (1024 - N)/64 
    		+ (1024 - N)%64/16
    		+ (1024 - N)%64%16/4
    		+ (1024 - N)%64%16%4;    	
    }    
}

发表于 2019-09-06 14:35:33 回复(0)

Java

咽喉上的刀

Java解答：

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int n = 1024 - N;
        int n1 = n/64;
        int n2 = n%64/16;
        int n3 = n%64%16/4;
        int n4 = n%64%16%4/1;
        int sum = n1+n2+n3+n4;
        System.out.println(sum);
    }
}

编辑于 2019-08-02 19:34:38 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师模拟算法工程师测试工程师 PHP工程师字节跳动 2019 数学 Java工程师

上传者：小小

难度：

14条回答 261收藏 22555浏览

通过挑战的用户

查看代码

牛客67485...

2023-09-04 12:46:44
Aquariu...

2023-03-14 17:35:59
求offer求排序过

2023-03-14 15:04:06
z84112938

2023-02-13 19:32:42
沉溺🌂

2023-02-13 17:17:46

找零

输入描述:

输出描述:

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题