分配饼干算法题C语言代码输出98与预期99不符排错

题目描述 #

假设你是一位很棒的家长，想要给孩子们分发饼干，每个孩子最多只能分配1块饼干。每个孩子 i 有一个胃口值 g[i]，即能让该孩子满足的饼干最小尺寸；每块饼干 j 有尺寸 s[j]，如果 s[j] >= g[i]，就可以将饼干j分配给孩子i，孩子会得到满足。你的目标是尽可能满足更多孩子，输出最多可满足的孩子数量。

示例 #

输入：g = [1,2,3], s = [1,1]
输出：1
解释：3个孩子的胃口值分别为1、2、3，2块尺寸为1的饼干只能满足胃口为1的孩子，因此输出1。

问题排查 #

你提供的代码运行测试用例输出98，预期输出99，存在以下两处核心逻辑错误：

错误1：胃口为0的孩子统计逻辑错误 #

代码开头直接遍历g数组，只要g[i]==0就直接给max计数加1，完全没有消耗对应的饼干：

for(int i=0;i<gSize;i++)
{
    if(g[i]==0)
    {
        max++;
    }
}

哪怕孩子胃口为0，也需要至少一块饼干（尺寸>=0）才能满足，该逻辑会导致无饼干可用时也错误统计了胃口为0的孩子，属于逻辑漏洞。

错误2：尺寸超过孩子最大胃口的饼干未被处理 #

代码处理饼干时仅判断了i<max1+1（max1是孩子的最大胃口值）的情况，对于尺寸大于所有孩子胃口的饼干，直接跳过没有处理：

if(i<max1+1)
{
    // 仅处理尺寸小于等于最大胃口的饼干
}
// 没有else分支处理更大尺寸的饼干

这类饼干明明可以满足任意未被满足的孩子，本次测试用例中存在这类饼干，刚好漏算1个可满足的孩子，导致输出比正确值少1。

其他非致命问题 #

• 循环内的if(i==0) {i++;}逻辑完全无用，因为循环i是从1开始遍历的，不可能等于0。
• 遍历查找可用孩子时每次都从j=1开始遍历，时间复杂度较高，可以优化为指针记录当前待匹配的最小胃口孩子，提升效率。
• 变长数组hash1[max1+1]、hash2[max2+1]在胃口/尺寸值很大时会出现栈溢出，建议改用动态内存分配或者排序+双指针的通用解法。

内容的提问来源于stack exchange，提问作者sind