蓝桥杯算法训练：ALGO232找零钱问题详解

问题背景

在日常生活中，找零钱是一个常见的问题。本题旨在通过模拟这一过程，训练使用贪心算法解决问题的能力。

题目描述

给定一系列顾客支付的金额，分别为25元、50元或100元。假设你初始时没有任何零钱，你需要为每个顾客提供正确的找零。如果可以完成所有顾客的找零，则输出“YES”，否则输出“NO”。

解决方案

使用贪心算法，优先使用大面额的零钱进行找零，以减少所需的零钱数量。

C语言代码实现

#include 

int main() {
    int n, i, a = 0, b = 0;
    scanf("%d", &n);
    for (i = 0; i         int tmp;
        scanf("%d", &tmp);
        if (tmp == 25) a++;
        if (tmp == 50) {
            if (a - 1 == -1) {
                printf("NO\n");
                return 0;
            }
            a--;
            b++;
        }
        if (tmp == 100) {
            if (a - 1 == -1) {
                printf("NO\n");
                return 0;
            }
            if (b - 1 == -1) {
                if (a >= 2) a -= 2;
                else {
                    printf("NO\n");
                    return 0;
                }
            } else {
                a--;
                b--;
            }
        }
    }
    printf("YES\n");
    return 0;
}

代码解析

1. 初始化变量`a`和`b`，分别表示25元和50元的数量。
2. 读取输入的顾客数量`n`。
3. 遍历每个顾客的支付金额`tmp`，根据金额的不同处理找零情况。
4. 如果当前金额为25元，直接增加25元的数量。
5. 如果当前金额为50元，检查是否有足够的25元进行找零，如果没有则返回“NO”。
6. 如果当前金额为100元，优先使用一个50元和一个25元进行找零，如果不够再尝试用三个25元找零。
7. 最后，如果所有顾客都能成功找零，输出“YES”。

样例运行结果

总结

通过本题，我们不仅掌握了贪心算法的基本思想，还学会了如何在实际问题中应用这种算法。希望本文对你有所帮助，如果有任何疑问，欢迎留言交流。

感谢支持

如果你觉得这篇文章对你有帮助，请记得点赞、关注和收藏。你的每一个支持都是我继续创作的动力！感谢大家的支持，下期更精彩！