学习目标

• 能把一对一分配问题转化为两个有序序列的匹配问题。
• 使用双指针实现“用最小的可行资源满足当前最小需求”的贪心策略。
• 能用交换论证说明当前选择不会减少最终满足的孩子数。

前置知识

• 数组排序与顺序遍历。
• 双指针的基本写法。
• 贪心选择性质与交换论证。

问题描述

有 n 个孩子和 m 块饼干。第 i 个孩子的胃口值为 g[i]，第 j 块饼干的尺寸为 s[j]。每个孩子最多得到一块饼干，每块饼干也最多分给一个孩子；只有当 s[j] ≥ g[i] 时，这块饼干才能满足该孩子。

请计算最多可以满足多少个孩子。

输入格式

• 第一行输入两个整数 n m，分别表示孩子数和饼干数。
• 第二行输入 n 个正整数 g[i]，表示每个孩子的胃口值。
• 第三行输入 m 个正整数 s[j]，表示每块饼干的尺寸；当 m = 0 时，这一行可以为空。

输出格式

输出一个整数，表示最多能够满足的孩子数。

约束

• 1 ≤ n ≤ 30000。
• 0 ≤ m ≤ 30000。
• 1 ≤ g[i], s[j] ≤ 2^31 - 1。
• 输入顺序不保证有序。

示例

示例 1：饼干不足

输入：

3 2
1 2 3
1 1

输出：

1

示例 2：饼干充足

输入：

2 3
1 2
1 2 3

输出：

2

思路提示

先把胃口值和饼干尺寸分别按升序排列，再用两个指针从最小值开始匹配。

• 如果当前饼干不能满足当前孩子，它也不可能满足胃口更大的孩子，因此只移动饼干指针。
• 如果当前饼干能够满足当前孩子，就完成一次匹配，并同时移动两个指针。

为什么不把一块大饼干直接给胃口更大的孩子？设当前最小胃口为 g，当前能够满足它的最小饼干为 s。如果某个最优方案把更大的饼干给了 g，可以把 s 与那块饼干交换；已满足的孩子数不会减少。于是总能得到一个包含当前选择的最优方案。

复杂度分析

• 时间复杂度：O(n log n + m log m)，主要来自两次排序。
• 额外空间复杂度：除输入数组和排序所需空间外，双指针部分为 O(1)。

测试设计提示

公开测试共 20 组，每组 5 分，总分 100 分。测试覆盖两个样例、没有饼干、单元素、重复值、无序输入、全部成功或失败、INT_MAX 数值边界，以及规模达到 30000 的压力数据。

运行与评分

在本 Lab 目录执行：

make doctor
make run
make score

如果没有 Make，也可以在仓库根目录执行：

pnpm lab:run -- labs/chapter-13/exercise/E-13-04-assign-cookies --target student

参考实现可以使用下面的命令验证：

pnpm lab:verify -- labs/chapter-13/exercise/E-13-04-assign-cookies --no-color

完成清单

• 正确读取两个数组，包括 m = 0 的情况。
• 分别对胃口值和饼干尺寸排序。
• 只用满足当前孩子的最小可行饼干完成匹配。
• 没有把一块饼干或一个孩子重复使用。
• 20 个公开测试全部通过，严格评分为 100/100。

思考与复盘

1. 为什么尺寸不足的当前饼干可以直接跳过？
2. 如果先满足胃口最大的孩子，算法还一定正确吗？如何证明或构造反例？
3. 如果每个孩子可以得到多块饼干，当前贪心策略的前提发生了什么变化？

题目来源

本题对应 LeetCode 455「分发饼干」：https://leetcode.cn/problems/assign-cookies/。本 Lab 将数组参数改写为标准输入输出格式。