C++ 中的分配饼干

分发饼干问题是一个简单的问题，它特别针对资源可用性有限的情况下，如何最大程度地满足需求。最初的编程面试题展示了贪心算法应用的几个关键原则。在这个问题中，我们有两个数组：第一个数组反映了孩子们“贪婪因子”，第二个数组是饼干的大小。目标是简单地将饼干分发给孩子们，以便在满足他们贪婪因子的前提下，尽可能多的孩子感到快乐，孩子的贪婪因子决定了孩子想要的最小饼干尺寸。

分发饼干问题很好地展示了贪心算法，并允许引入排序和已排序资源的顺序分配。它在最优控制等应用中形成了一项关键技术，我们必须在诸如汇总财务、管理计算机负载以及许多其他资源有限的计算问题中找到最佳解决方案。这种结构化的高效方式为在计算机科学和实际生活中解决其他各种优化和分配问题奠定了基础。

同样，每块饼干都有一个预设的尺寸，定义了它满足孩子需求的潜力。目标是让尽可能多的孩子快乐，并且每个孩子最多获得一块饼干，每块饼干最多给一个孩子。这种情况模仿了现实生活中的资源分配场景，其中有限的资源必须分配给少数有特定需求的收件人或用户。

分发饼干问题的解决方案采用了称为贪婪因子的特定策略，其中贪婪因子和饼干尺寸都按递增顺序排列。排序使得匹配过程协调一致，为满足每个孩子的最低可能份量以满足贪婪标准提供了机会。组合式首次拟合算法在每次迭代时从最贪婪的因子开始；它将孩子分配到它的饼干中，只有在找到足够大的饼干来满足当前孩子时，才会移动到下一个孩子。这种方法确保小饼干分给贪婪程度较低的孩子，同时将大饼干留给贪婪的孩子。

方法：双指针技术

使用双指针方法，解决方案同时遍历两个数组。假设一块饼干满足了孩子的贪婪需求。在这种情况下，孩子的列表指针会变绿，表示孩子已满足，再次组织孩子的列表，并将孩子和饼干列表的指针都向前移动到下一个元素。

如果当前孩子没有得到饼干，只有饼干指针会向前移动，寻找一个可能满足孩子的更大饼干。匹配过程将持续进行，直到所有可用的分配都已完成，或者直到饼干都用完为止。

程序

让我们举一个例子来说明如何使用双指针技术在 C++ 中分发饼干。

输出

 
Sorted Greed Factors: 1 2 3 
Sorted Cookie Sizes: 1 1 
Checking if cookie of size 1 can satisfy child with greed 1.
Child with greed 1 is satisfied by cookie of size 1.
Checking if cookie of size 1 can satisfy child with greed 2.
Cookie of size 1 is too small for child with greed 2.
Total content children: 1
Example 1:
Greed factors: 1 2 3 
Cookies: 1 1 
Number of content children: 1
Sorted Greed Factors: 1 2 
Sorted Cookie Sizes: 1 2 3 
Checking if cookie of size 1 can satisfy child with greed 1.
Child with greed 1 is satisfied by cookie of size 1.
Checking if cookie of size 2 can satisfy child with greed 2.
A child with Greed 2 is satisfied by a cookie of size 2.
Total content children: 2
Example 2:
Greed factors: 1 2 
Cookies: 1 2 3 
Number of content children: 2
Sorted Greed Factors: 1 2 3 
Sorted Cookie Sizes: 2 
Checking if cookie of size 2 can satisfy child with greed 1.
Child with greed 1 is satisfied by cookie of size 2.
Total content children: 1
Example 3:
Greed factors: 1 2 3 
Cookies: 2 
Number of content children: 1   

说明

该程序以正确的方式在两个列表之间取得平衡，以使孩子们感到尽可能满意。

1. 输入验证

程序的第一行调用 `validateInputs`。此函数检查 `greedFactors` 和 `cookieSizes` 是否已正确初始化为所有非负值。如果检测到负值，将显示错误消息，并且该函数会提前退出，以防止处理无效数据。此验证步骤对于保持原始数据的完整性以及通过程序执行获得可靠结果至关重要。

2. 排序以实现最佳匹配

之后，在验证输入数据后，将调用主函数 `findContentChildren` 来处理数据。在该函数中，我们首先将 `greedFactors` 和 `cookieSizes` 列表按升序排序。为了实现高效的分配过程，我们将饼干排序，以便最小的饼干分给最不贪婪的孩子，将更大的饼干留给需求更多的孩子。这就是为什么我们需要这种战略性排序来最优地分配饼干。因此，他们将最大化满意孩子的数量。

3. 双指针技术

双指针技术，以及 `childIndex` 和 `cookieIndex`，是解决方案的核心。这些指针遍历 `greedFactors` 和 `cookieSizes`。每次程序进行迭代时，它都会检查 `cookieIndex` 处的饼干是否足以满足 `childIndex` 处孩子的实际贪婪程度需求。只有当满足时，孩子才会高兴，两个指针都会前进，然后移动到下一个孩子和饼干。

这通过 `contentChildren` 属性的计数增量 `contentChildren` 来反映。但是，如果饼干不够，只有 `cookieIndex` 指针会向前移动到该孩子可用的下一个饼干。这确保了饼干得到了有效利用。在饼干中，较小的尺寸会首先被记录下来，以便于跟踪和调试，并降低使用较大尺寸饼干的孩子的贪婪程度。

4. 功能演示

`runExamples` 函数首先通过展示几个测试用例来演示代码的健壮性，每个测试用例都描绘了不同的情况。有许多饼干的案例，有少量饼干的案例，以及贪婪程度恰好与饼干尺寸匹配的案例。

我们使用 `findContentChildren()` 函数运行每个测试用例，并使用 `displayResult()` 函数以结构化的形式打印出结果。这个函数的主要作用是整齐地输出贪婪因子、饼干以及满意孩子的总数。

复杂度分析

时间复杂度

时间复杂度可以细分为几个组成部分，反映了算法执行的主要操作。

• 输入验证：首先检查 `greed factor` 和 `cookieSizes` 向量的每个元素是否为非负值。`validateInputs` 函数会遍历这两个列表以执行此操作。此步骤的复杂度为 O(n+m)，其中 n 是孩子的数量，m 是饼干的数量。这种线性检查对于验证输入至关重要，以便在处理主要步骤时不会捕获错误。
• 排序：验证输入后，算法使用 C++ 标准库的 `std::sort` 来排序两个向量。对于 `greedFactors`，排序算法的平均情况时间复杂度为 O(n log n)；对于 `cookieSizes`，复杂度为 O(m log m)。由于匹配是排序向量的关键操作，因此我们可以说对两个向量进行排序的总复杂度为 O(n log n + m log m)。此排序步骤有助于解决我们不知道哪些饼干最小，哪些孩子最不贪婪的问题，从而使我们能够轻松找到最不贪婪的孩子和他们之中最小的饼干。
• 双指针遍历：算法的内层循环是算法的核心；它在遍历排序列表时会迭代两个指针（`childIndex` 和 `cookieIndex`）。我们会一直循环，直到其中一个指针到达相应列表的末尾。在最坏的情况下，每个指针都会遍历整个数组，因此这部分的时间复杂度为 O(n+m)。因此，这是饼干匹配阶段，它会将饼干与孩子进行匹配，并且我们进行匹配的顺序会是将贪婪的孩子与饼干进行匹配，以最大化我们可以取悦的孩子数量。

算法的总运行时间为 O(n log n + m log m)。

空间复杂度

分析空间复杂度涉及评估算法使用的内存。

• 输入存储：`greedFactors` 和 `cookieSizes` 向量存储输入数据。由于它们包含所有贪婪因子和饼干尺寸，因此其空间复杂度为 O(n+m)。
• 辅助空间：算法不使用随输入大小增长的附加数据结构。虽然排序算法可能需要一些堆栈空间用于递归调用，但与输入大小相比，这通常可以忽略不计，因此辅助空间复杂度为 O(1)。

总空间复杂度仍由输入存储主导：O(n+m)