鱼C论坛

 找回密码
 立即注册
查看: 5080|回复: 35

[技术交流] NOI题目 换钞票

[复制链接]
发表于 2021-7-7 12:16:37 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 青出于蓝 于 2021-7-8 17:22 编辑

题目描述
将任意给定的整百元钞票,兑换成10元、20元、50元小钞票形式。输出兑换方案总数。


输入
输入需要兑换的钞票总数n。

输出
输出方案总数。

样例输入

100

样例输出

10


提示
方案序号10元张数20元张数50元张数100220503121424053116430750186209810101000

这里用的c++ 如果鱼友们有其他语言的答案,会评分置顶

答案及思路如下:
游客,如果您要查看本帖隐藏内容请回复

如有问题,欢迎探讨

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2021-7-8 09:01:27 | 显示全部楼层
利用其他语言答对题目可置顶并评分。
欢迎订阅此专辑,目前可参与维护
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-8-19 20:42:53 | 显示全部楼层
题主你的思路挺有意思的,也是直入思考的一种方式,不过如果数据量过大,程序测试用例如果要求苛刻的话,可能会通不过这个程序。显示超时。
如果后面你学习了数据结构与算法的话,你会知道你的程序的时间复杂度是O(n^3),这是一个很吓人的概念了。感兴趣可以自己找个视频或者找百度百科或者维基百科看看,因为不知道你多大,和学习模式,这个你自己去寻找啦。
下面分享以下我的思路:
钞票有三种规格,10,20,50。 其实我们仔细思考能够发现,20 可以拆分成 20 or 2 * 10两种方案, 50 可以拆分成 5 * 10 or 20 + 3 * 10 or 2 * 20 + 10 or 50 这四种方案。
这对我们的题目有什么启发呢?
假设我能够尽量使用50的钞票,我能不能通过上面的方案分析来判断我能有多少种可能性呢?
能不能知道一种尽量使用50然后再使用20最后用10的钞票进行填补的方案呢?
假设我们最后得到的结果是 50a1 + 20a2 + 10a3(这里的a1, a2, a3代表的是钞票的数量;经过计算,理论上是可以求得的。)
最后的方案总数应该是我们对50和20钞票进行拆分后的结果;也就是a1*a2;
好了,这是假设。我们再举几个实际的例子来测试检验下,80,90,100,110,120
Oh, shit.... 我的思考过程错误了。 如果 50 = 2* 20 + 10 ,有两张的话, 50 *2 = 2 * 20 + 10 + 2 * 20 + 10 其实漏了一种情况, 两个10可以合并成一个20....

最后,我看了下别人如何写的,发现楼上的代码很优美,思路是从最少的开始找起,再填20,最后补充没有20情况的下
ans += (n-i*50)/20 + 1;
核心是这个,能不能理解。
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int ans = 0;       
    for(int i=0; i<=n/50; i++)
    {
        ans += (n-i*50)/20 + 1;
    }
    cout << ans<< endl;
    return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-7 12:59:59 | 显示全部楼层

回帖奖励 +1 鱼币

这有点意思
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-7 16:15:40 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-7-7 17:09:54 | 显示全部楼层
学习学习,以后用得着
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-7 17:12:19 | 显示全部楼层

学习学习,以后用得着
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-7 17:14:14 | 显示全部楼层
为什么我没有币
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-7 17:19:27 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-7-7 17:22:37 | 显示全部楼层
不要说我灌水啊,新人领个币可真难
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-7 17:36:19 | 显示全部楼层
这命中率~  我脸真黑~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-7 17:53:42 | 显示全部楼层
楼主能删楼层的帖子么     帮我把前面的都删了吧,丢人~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-7 19:38:35 | 显示全部楼层
我来抽奖了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-7 19:42:16 | 显示全部楼层
这肯定有问题啊

评分

参与人数 1鱼币 +2 收起 理由
青出于蓝 + 2 安慰安慰[笑]

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-7 20:57:40 From FishC Mobile | 显示全部楼层

回帖奖励 +1 鱼币

来看看。。。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-8 00:07:27 | 显示全部楼层

感谢楼主赏我的两个币,感动哭了~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-8 00:08:37 | 显示全部楼层
我再试试~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-8 08:31:24 | 显示全部楼层
来个
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-7-8 10:48:26 | 显示全部楼层
来看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-8 10:50:54 | 显示全部楼层

回帖奖励 +1 鱼币

是不是每个人领的数量是有限的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-8 10:54:28 | 显示全部楼层

回帖奖励 +1 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-6-19 01:10

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表