论坛 › C\C++交流 › NOI题目 换钞票

xiongdy 发表于 2021-7-8 21:14:23

有意思

芬里尔ming 发表于 2021-7-9 16:02:55

{:10_254:}

yangtao120 发表于 2021-7-10 08:48:12

每个人都可以吗

赚小钱 发表于 2021-7-10 17:40:29

void exchange(int target, int *units, int length, int *res);

void dfs(int target, int *units, int length, int *res);

int main(int argc, char *argv[]) {
    int coins[] = {1, 2, 5};
    for (int target = 1; target <= 20; target++) {
      int result = 0;
      exchange(target, coins, sizeof coins / sizeof coins, &result);
      printf("target: %3d\t-> %3d\n", target, result);
    }
}

void exchange(int target, int *units, int length, int *res) {
    if (0 == target) {
      return;
    }
    dfs(target, units, length, res);
}

void dfs(int target, int *units, int length, int *res) {
    if (0 == target) {
      *res = *res + 1;
      return;
    }
    for (int i = 0; i < length; i++) {
      if (units > target) {
            continue;
      }
      dfs(target - units, units, length, res);
    }
}

需要对结果去重

chenyiyun 发表于 2021-7-10 19:08:53

#include <bits/stdc++.h>
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;
}

一只咸鱼123 发表于 2021-7-10 20:07:32

开

thekfjie 发表于 2021-7-10 20:35:38

来看看

antonybear 发表于 2021-7-12 16:26:15

来学习了

wfuhkd 发表于 2021-7-12 21:26:01

学习

1842771885 发表于 2021-7-12 22:40:50

这不是我的期末考试题目么。。。。。考c的。。。

夜晖 发表于 2021-7-13 09:00:53

{:10_316:}

Justin1 发表于 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;
}

青出于蓝 发表于 2021-8-19 21:18:15

Justin1 发表于 2021-8-19 20:42
题主你的思路挺有意思的，也是直入思考的一种方式，不过如果数据量过大，程序测试用例如果要求苛刻的话，可 ...

能理解的，这种方法比较好。把大面值的钞票拆分，就可以大大减小计算量。
自己写的方法在有些题库里用确实过不了，简单的枚举，甚至忽略了钞票是整百这个条件。
谢谢！学到了{:10_303:}

刻斯不会菲 发表于 2021-9-30 15:24:05

。

初久i 发表于 2021-11-4 15:39:30

想看以下

tomok 发表于 2021-11-5 08:55:45

谢谢分享

查看完整版本: NOI题目 换钞票