C++ 中的柠檬水摊位找零挑战

交易处理是杂货店、自动售货机和我们的柠檬水摊每天都会遇到的一个重要的常见问题。柠檬水摊找零挑战是一个明确定义的算法问题，在现实世界中，适当的找零管理需要实时动态地分配找零，并在即时找零决策时受到资源限制。这个问题乍看起来很简单，但需要批判性的实时决策能力，这与供应商的运营和收银机的职责息息相关。

在我们经营柠檬水摊的过程中，我们以每杯 5 美元的价格出售饮料。付款方式接受 5 美元、10 美元和 20 美元的纸币，方便顾客使用。在买家收到他们想要的钱之前，卖家必须从之前顾客收到的钱中找给顾客正确的零钱。为了做好高效找零的准备，他需要能够跟踪现有的面额并做出即时的找零类型决策。然而，目标仍然是为顾客提供良好的服务，顾客永远不会缺乏足够的零钱。

最后，贪心算法方法是解决这类现实问题的一种强大方法。程序员通常采用工作流程方法来生成最佳结果，但在贪心算法中，程序员在每个处理阶段都会选择即时有利的路线。因为一开始会用较大的面额纸币作为找零，这有助于为将来的需求保留小面额纸币。

问题陈述

柠檬水摊找零问题通过以下陈述在数学上定义：公司将每份柠檬水定价为 5 美元。一群顾客在付款购买柠檬水之前出现，他们使用 5 美元、10 美元或 20 美元的纸币付款。我们需要验证，使用早期顾客支付的钱找给所有顾客正确的零钱是否仍然可能。总金额受限于顾客之前的支付，因为资金是您唯一可用的找零来源。

这个问题有几个基本组成部分，我们将进行讨论。

输入

问题的开头使用整数来表示顾客购买柠檬水的成本。顾客通过“5 5 10 20”这样的交易序列付款，其中第一次付款包含一张 5 美元的纸币，第二次付款包含另一张 5 美元的纸币，接着是一张 10 美元的纸币，然后第四次付款使用了一张 20 美元的纸币。

输出

系统生成布尔输出，正确找零会产生 true 响应，如果向任何顾客提供错误的找零，则出现 false。

规则和约束

• 我们的系统需要为每次付款提供找零，直到所有顾客完成付款序列。
• 我们开始时没有现金储备，因此我们的纸币收集池在整个过程中保持完全为空。
• 库存找零选项仅通过收集顾客现金支付的交易款项产生。

目的

需要评估当前规则是否允许为每一位等待的顾客提供付款服务。如果未能向顾客提供合适的找零，操作将失败。

示例 1

输入 [5, 5, 5, 10, 20]

输出： true

说明

• 由于前三位顾客支付了 5 美元的纸币，我们不需要找零。现在，我们有三张 5 美元的纸币。
• 第四位顾客支付了十美元。在找零 5 美元时，我们必须使用一张 5 美元的纸币，同时保留其余的两张 5 美元的纸币和一张 10 美元的纸币。
• 在第四位顾客支付了 20 美元后，另一位顾客支付了 20 美元。支付一张 10 美元纸币加上一张 5 美元纸币，我们给出了 15 美元的不正确找零，因为我们保留了一张剩余的 5 美元纸币。
• 我们所有的顾客在当天都没有收到不满意的服务，这使得最终输出真正成功。

示例 2

输入 [5, 5, 10, 10, 20]

输出： false

说明

• 第一位和第二位顾客都给了我们 5 美元的纸币，所以我们不需要找零。现在，我们有两张 5 美元的纸币。
• 尽管只有一张 10 美元的纸币作为支付，第三位顾客还是选择了交易。我们给他们一张 5 美元的纸币作为找零，这让我们剩下了一张 5 美元的纸币和一张 10 美元的纸币。
• 第四位顾客用一张 10 美元的纸币完成了付款。最后一张 5 美元的纸币给了顾客，但我们剩余的现金只有一张 10 美元的纸币。
• 第五位顾客支付了 20 美元，用了一张崭新的 20 美元纸币。我们必须通过收到一张 10 美元的纸币加上一张 5 美元的纸币来找零 15 美元。STP 显然失败了，因为我们没有足够的 5 美元纸币来满足我们最后一位顾客的付款。输出为 false。

所提出的问题结合了教育价值和一个有趣的 数组 复杂性。交易序列至关重要，因为不同的顾客组织在某些支付组合下可能会成功，但在其他组合下可能会失败。我们在开业初期分配 10 美元和 20 美元纸币的方式决定了未来为顾客有效服务的容量。这项任务展示了战略规划和资源管理为何对成功至关重要。

贪心算法是解决这个问题的最有效方法。在找零时，有必要先使用最大面值的纸币。当顾客使用 20 美元的纸币付款时，用一张 10 美元加上一张 5 美元进行交易，而不是用多张 5 美元纸币进行交易，这样更有意义。这种方法通过为未来的付款提供更好的可用性来节省小面额纸币。

柠檬水摊找零问题既为掌握贪心算法的执行提供了一个机会，也提高了我们解决实际情况中资源管理问题的能力。

方法和解决方案

然而，贪心算法可以解决柠檬水摊找零问题。这种方法优化了资源分配，使得顾客的金库中可用的钱可以用于未来的客户交易。

关键思想

显然，贪心策略是先通过提供最大可能面值的纸币来找零给顾客。小面额纸币在未来的现金交易中得到使用，并且该策略会保留它们。

例如

• 与其找给某人三张 5 美元的纸币作为找零，不如提供一张 10 美元的纸币和一张 5 美元的纸币作为 15 美元的找零。
• 如果我们需要找 5 美元，我们只能给一张 5 美元的纸币。
• 这种付款方式允许小面额纸币与任何失去使用的货币类型一起保留。

解决方案的步骤如下：

初始化计数器

通过两个 变量 系统存储我们当前的 5 美元和 10 美元账户，我们的其他纸币是它们的倍数。例如，five_count 和 ten_count。

遍历顾客

因此，我们处理付款的步骤必须是先顾客。对于每次付款，

• 当顾客支付 5 美元的纸币时，增加 five_count。
• 当顾客支付 10 美元的纸币时，将 five_count 减去 5（用于找零），然后增加 ten_count。
• 尽可能先使用较大的 20 美元纸币与较小的 10 美元纸币，然后保留较小的 5 美元纸币。当 10 美元纸币不可用时，使用三张 5 美元纸币。

检查找零不足

如果无法找零，则以 false 返回结束付款验证。

返回结果

如果为 true，则为所有顾客返回成功结果。

示例

让我们以一个例子来说明 C++ 中的柠檬水摊找零问题。

输出

Test case 1: True
Test case 2: False
Test case 3: False
Test case 4: True
Test case 5: False
Test case 6: True   

结论

总之，柠檬水摊找零问题有助于发现关于资源使用和组织决策的重要管理实践。它能有效地找出是否能为所有顾客服务，并为所有顾客提供准确的找零。这是通过贪心算法实现的。改变这样一个过程是找零管理的基本策略之一。这意味着首先选择最大的纸币，以便其他顾客可以继续获得一些小面额纸币。

这种情况凸显了确保在所有支付场景下，无论是否有无现金收银机和 20 美元纸币的顾客交易，所验证的解决方案都有效的重要性。该解决方案对于输入大小为 n 次交易和音调大小来说，运行时间也为O(n)。

然而，它超越了代码创建，解决了适用于现实世界中资源有限且通过渐进式操作进行管理的场景的可部署决策框架。开发人员有了一种高效的算法创建方法，能够完美地兼顾性能和准确性。

柠檬水摊找零问题完整地展示了基本的监管结构如何产生引人注目的计算挑战。基本算法被介绍给学生，并与现实生活中的相关性相结合，这个问题非常适合作为新学生的有效练习。