NOI题目 换钞票
本帖最后由 青出于蓝 于 2021-7-8 17:22 编辑题目描述
将任意给定的整百元钞票，兑换成10元、20元、50元小钞票形式。输出兑换方案总数。
输入
输入需要兑换的钞票总数n。
输出
输出方案总数。
样例输入
100
样例输出
10
提示
方案序号10元张数20元张数50元张数100220503121424053116430750186209810101000
这里用的c++{:5_93:} 如果鱼友们有其他语言的答案，会评分置顶
答案及思路如下：
思路，列举在n元以下所有情况，依次排除
#include <iostream>
using namespace std;
int main()
{
int n,num;
cin>>n;
n=n/10;
num=0;
for (int i=0;i<=n/5;i++){
for (int a=0;a<=n/2;a++){
for (int b=0;b<=n;b++){
if (50*i+20*a+10*b==10*n)
num++;
}
}
}
cout<<num;
return 0;
}
如有问题，欢迎探讨 利用其他语言答对题目可置顶并评分。
欢迎订阅此专辑，目前可参与维护 题主你的思路挺有意思的，也是直入思考的一种方式，不过如果数据量过大，程序测试用例如果要求苛刻的话，可能会通不过这个程序。显示超时。
如果后面你学习了数据结构与算法的话，你会知道你的程序的时间复杂度是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;
}
这有点意思 {:5_95:} 学习学习，以后用得着
学习学习，以后用得着 为什么我没有币 {:10_247:}{:10_247:}{:10_247:} 不要说我灌水啊，新人领个币可真难{:10_266:}{:10_266:}{:10_266:} 这命中率~我脸真黑~{:10_245:}{:10_245:}{:10_245:} 楼主能删楼层的帖子么{:10_266:}{:10_266:} 帮我把前面的都删了吧，丢人~ 我来抽奖了 这肯定有问题啊 来看看。。。。。 超级玛尼哄 发表于 2021-7-7 19:42
这肯定有问题啊
感谢楼主赏我的两个币，感动哭了~ 我再试试~{:10_254:}{:10_254:} 来个 来看看{:10_254:} 是不是每个人领的数量是有限的 {:10_254:}
页:
[1]
2