首页 > 试题广场 >

找零

[编程题]找零
  • 热度指数：28934 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为的商品，请问最少他会收到多少硬币？

输入描述:
一行，包含一个数N。


输出描述:
一行，包含一个数，表示最少收到的硬币数。
示例1

输入

200

输出

17

说明

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

备注:
对于100%的数据，。
算法知识视频讲解
开通博客
头像 白色高跟鞋
发表于 2020-04-27 22:00:52
模拟+贪心 因为存在一元硬币，一定可以找清，所以直接贪心 N = int(input()) remain, cnt = 1024-N, 0 coins = [64, 16, 4] # coins which values greater than 1 for i in range(len(co 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 北晨LPL
发表于 2020-06-21 10:21:21
c++ #include<iostream> using namespace std; int main() { int n,a = 1,b = 1,c = 1,d = 1,sum = 0; cin>>n; n = 1024 - n; a = 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 laglangyue
发表于 2020-06-11 17:02:35
最值问题一般两个思路，贪心和dp本题显然也可以通过dp求解，与斐波那契数列的思路一致：构建数组int[1024],表示最少硬币数dp[n]=min(dp[n-64]，dp[n-16]，dp[n-4]，dp[n-1])，注意小于64取后三项，小于16取后两项如果是多个测试用例一起，这样会很快，因为只要 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 怕浪猫
发表于 2022-08-26 23:57:19
javascript 牛客变风格了啊 let N = readline() let coinCount = 0 let sum = 1024 - N; while(sum > 0){ if(sum >= 64){ coinCount++ sum - 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 爱编程的机器猫
发表于 2022-02-14 19:56:56
一个简单的贪心问题，用c++解决 思路： 需要找零的钱从大面值的开始减，如果不够减就换小面值的钱继续减，知道剩下找零的钱减到零为止。 #include<bits/stdc++.h> using namespace std; int main() { int n; cin >& 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客128598828号
发表于 2022-08-05 22:05:48
1024-N得到找零总数，用它除以64得整数a1和余数a2，a2除以16得整数b1和余数b2，b2除以4得到c1、c2，c2除以1得到d1，最后把a1,b1,c1,d1相加即可得到结果。 #include<iostream> using namespace std; 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 ꧁Binge꧂
发表于 2022-03-23 22:45:31
杨辉三角形 如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1,⋯ 给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？ 输入描述 输入一个整数 N。 输出描述 输出一个整数代表答 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 ꧁Binge꧂
发表于 2021-12-18 10:17:58
贪心算法求解 获取输入商品价值，求得需要找的钱 看需要找零的钱满足最大面值的硬币几个，从总价值中减去相应价值 不断循环求解，每一次都是贪心求解当前面值的硬币最多使用的个数 具体C++代码如下： #include<iostream> using namespace std; int 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客289281343号
发表于 2020-04-28 09:12:36
解题思路：贪心思想，找零的硬币值越大，得到零钱的个数就越少。import java.util.*;public class Main{ public static void main(String arg[]){ Scanner scan=new Scanner(System.i 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 苏觅云
发表于 2022-05-22 22:04:40
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = 102 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 模拟 算法工程师 测试工程师 PHP工程师 字节跳动 2019 数学 Java工程师
上传者：小小
难度：
144条回答 19616浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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