|
发表于 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情况的下
核心是这个,能不能理解。
- #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;
- }
复制代码
|
|