喵哈喽~ 主人，欢迎来到本喵的题解小课堂！今天我们要看的是一道非常可爱的入门题，Codeforces 上的 996A - Hit the Lottery。别看它只是个 A 题，里面可是藏着重要的算法思想哦。快搬好小板凳，让本喵给你细细道来吧，喵~ 🐾

题目大意

这道题是说，有一个叫 Allen 的大富翁，他银行里有 n 美元的存款。出于安全考虑（本喵猜是想买好多好多小鱼干！），他想把所有的钱都取成现金。美元的纸币面额有 1 美元、5 美元、10 美元、20 美元和 100 美元这五种。

问题是：Allen 最少能收到多少张纸币呢？

举个栗子🌰：

• 如果 Allen 有 125 美元，他可以取一张 100 美元的，一张 20 美元的，和一张 5 美元的。总共 3 张，不能再少啦。
• 如果他有 43 美元，他可以取两张 20 美元的，和三张 1 美元的。总共 5 张。

是不是很简单喵？就是要想办法用最少的纸币凑出 n 元钱啦~

题解方法

本喵的直觉告诉我，要用最少的纸币，那肯定要尽可能多地使用大面额的呀！这就像吃自助餐，肯定先冲向最贵的刺身区，对不对？这种策略在算法里有一个专门的名字，叫做 贪心算法 (Greedy Algorithm)。

对于这道题，我们的贪心策略非常直接：

1. 先看 100 元的：看看 n 元最多能换多少张 100 元的，全部换掉。
2. 再看 20 元的：用上一步剩下的钱，看看最多能换多少张 20 元的。
3. 然后是 10 元的：继续用剩下的钱换 10 元的。
4. 接着是 5 元的：同上。
5. 最后是 1 元的：最后不管剩下多少（肯定小于5元），就只能用 1 元的来补齐了。

我们用 n = 125 来模拟一下这个过程：

• Step 1 (100元): 125 / 100 = 1。可以换 1 张 100 元的。剩下 125 % 100 = 25 元。
• Step 2 (20元): 25 / 20 = 1。可以换 1 张 20 元的。剩下 25 % 20 = 5 元。
• Step 3 (10元): 5 / 10 = 0。换不了 10 元的。剩下 5 % 10 = 5 元。
• Step 4 (5元): 5 / 5 = 1。可以换 1 张 5 元的。剩下 5 % 5 = 0 元。
• Step 5 (1元): 剩下 0 元，不需要 1 元的了。

总张数就是 1 + 1 + 0 + 1 + 0 = 3 张。和样例一模一样，搞定，喵！这种方法总是能得到最优解，因为这些纸币的面额设计得非常巧妙。

题解

好啦，现在让本喵带主人看看代码是怎么用爪爪敲出来的吧，喵~

#include <iostream>

int main() {
    // 这是一个让输入输出更快的魔法，喵~ 在比赛里很有用哦！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // Allen 的钱可能会很多（最多10^9），用 long long 是个好习惯，
    // 可以防止数字太大溢出。虽然这题 int 也够啦，但有备无患总是好的，喵。
    long long n;
    std::cin >> n;

    // 准备一个计数器 count，用来数我们总共用了多少张纸币。
    long long count = 0;

    // 贪心第一步：换100元大钞！
    // n / 100 能算出最多能换多少张。
    // 我们把换到的张数加到 count 里。
    count += n / 100;
    // n %= 100 则是算出换完之后还剩下多少零钱，用于下一步计算。
    n %= 100;

    // 贪心第二步：用剩下的钱换20元的。
    count += n / 20;
    n %= 20;

    // 贪心第三步：换10元的。
    count += n / 10;
    n %= 10;

    // 贪心第四步：换5元的。
    count += n / 5;
    n %= 5;

    // 最后剩下的钱肯定小于5元啦，那就只能用1元的来付了。
    // 剩下多少钱，就需要多少张1元的，所以直接加上 n 就好啦。
    count += n;

    // 把总张数 count 打印出来，就大功告成啦！
    std::cout << count << std::endl;

    return 0;
}

知识点介绍：贪心算法

这道题的核心思想就是 贪心算法 (Greedy Algorithm)，听起来是不是很厉害，喵？

什么是贪心算法？

贪心算法呀，就是在解决问题的每一步中，都采取当前状态下看起来最好或最优的选择，从而希望最终能导致全局结果是最好或最优的。

就像一只看到小鱼干就马上扑过去的小猫，只看眼前最好的选择，喵~ 在这道题里，"当前最好的选择" 就是用面额最大的纸币。

贪心算法并不总是最优解

但是主人要注意哦，贪心不是万能的！有时候只看眼前利益，可能会吃大亏的。这种找零钱的问题，如果面额设计得不好的话，贪心就会出错。

举个反例：

假设我们有面额为 {1, 3, 4} 的硬币，要凑出 6 元。

• 贪心策略：先拿最大面额的。我们会先拿一个 4 元，然后剩下 2 元。为了凑齐 2 元，只能拿两个 1 元的。总共是 4 + 1 + 1，需要 3 枚硬币。
• 最优解：实际上，我们可以拿两个 3 元的硬币，3 + 3 = 6，只需要 2 枚硬币。

看到没？贪心策略在这里就不是最优的了。

为什么这道题可以用贪心？

那为什么我们这道题又可以大胆地用贪心了呢，喵？

因为美元的这些面额 {1, 5, 10, 20, 100} 设计得非常标准和巧妙。它们满足一个很好的性质：任意一个面额都是比它小的面额的倍数 (或者说，用小数额的纸币凑成一个大数额纸币时，不会产生更优的组合方式)。

简单来说，为了凑齐 100 元，你用一张 100 元的纸币（1张），永远比用 20 元的（5张）或 10 元的（10张）要划算。你永远不会遇到“我少用一张大面额，多用几张小面额反而总数更少”的情况。这种性质保证了我们每次贪心地选择最大面额，都不会错过最优解。

所以，大胆地贪心吧，喵！

好啦，这道题的讲解就到这里啦！是不是很简单呢？主人下次遇到类似的问题，也要像本喵一样，先看看能不能用贪心爪爪解决哦！喵~ ❤️