LeetCode LCP 18. 早餐组合

约 10 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 百度
标签
数组 排序 双指针 二分查找 LCP
目录

题目描述

✅ LCP 18. 早餐组合

题意分析

给两份价目表：主食价格数组和饮料价格数组。要从主食里挑一份、饮料里挑一份，使两者价格之和不超过预算 $x$，问这样的搭配一共有多少种，结果对 $1000000007$ 取模。

「搭配」是按下标区分的：两份价格相同的主食算作两个不同的选择，所以数的是下标对的数量，而不是价格组合的种类，不需要去重。

约束信号有两层。两个数组长度都能到 $10^5$，直接双重循环是 $10^{10}$ 次判断，必然超时，所以要么排序后用有序性加速，要么换成计数前缀和。答案的量级同样是 $10^{10}$，早已越过 32 位整数的上界，所以累加过程必须用 64 位承接并及时取模——题目给出取模要求本身就是在提示这一点。

边界要点清楚：某份主食的价格可能已经等于甚至超过预算，此时它配任何饮料都不成立（价格都是正数），贡献为零；预算可能小到任何搭配都不成立，答案为 0；两个数组各自的长度可能相差悬殊，这会影响「对谁排序、对谁遍历」的取舍。

解法：排序 + 二分计数

核心思路

最直接的做法是双重循环：对每一份主食，遍历所有饮料检查价格之和是否超预算。它是对的，但 $O(nm)$ 在 $10^5$ 量级下完全跑不动。浪费在于，对每一份主食都把整份饮料价目表从头扫了一遍，而这些扫描其实高度重复。

关键观察是：一旦固定了主食价格 $s$，合法的饮料就是所有满足 $d \le x-s$ 的那些，这是一个纯粹的「有多少个数不超过给定阈值」的计数查询。而这类查询在有序数组上可以用二分在 $O(\log m)$ 内完成——只要把饮料价格排一次序，之后每次查询都能复用这份有序性。

所以整体结构是：排序一次，然后对每份主食做一次二分，把答案累加起来。因为每份主食的选择相互独立，乘法原理保证「对每份主食分别数出合法饮料数再求和」不重不漏地覆盖了全部搭配。

二分这一步要找的是 upperBound，也就是第一个严格大于阈值的位置，这个下标恰好等于不超过阈值的元素个数。实现上维护左闭右开区间 $[l,r)$，并保持这条不变量：所有下标小于 $l$ 的元素都不超过阈值，所有下标不小于 $r$ 的元素都严格大于阈值，答案位置始终落在 $[l,r]$ 内。 初始 $l=0$、$r=m$，此时两个断言都是空真；每轮取中点 $mid$，若 arr[mid] <= target 就说明 $mid$ 及其左侧都合法，令 $l=mid+1$；否则 $mid$ 及其右侧都不合法，令 $r=mid$。两种更新都维持了不变量，且区间长度严格缩小，循环终止于 $l=r$，此时它就是分界点。

累加时每加一次就取一次模，把结果压回 $10^9$ 以内，避免 $10^5$ 次累加把 64 位也撑爆。

解题步骤

  • 对饮料价格数组排序。为什么只排饮料不排主食：主食只需要被逐个遍历，遍历顺序不影响求和；而饮料要被反复查询，必须有序才能二分。
  • 遍历每一份主食价格 $s$，若 $s \ge x$ 直接跳过。为什么可以跳过：饮料价格都是正数，主食已经吃掉全部预算时任何搭配都超标；这一步严格来说只是剪枝，即使不写，后面算出的阈值为非正数时二分也会返回 0。
  • 计算阈值 $\textit{remain}=x-s$，对排好序的饮料数组求 upperBound(remain)。为什么这个返回值就是个数：由不变量，最终的 $l$ 左侧全部不超过阈值、右侧全部超过阈值，所以 $l$ 同时是分界下标和合法元素的数量。
  • 把这个个数累加进答案并立即取模。为什么要立即取模：答案上限是 $10^{10}$，若用 32 位会溢出；即便用 64 位，逐步取模也能让中间值始终很小，是更稳的习惯。
  • 遍历结束后把 64 位的累加值转回 32 位返回。为什么转换安全：取模后的值一定在 $[0,\ 10^9+6]$ 内，落在 int 范围。

以 staple = [7, 11, 3]、drinks = [4, 9, 6]、x = 12 走一遍：先把饮料排序得到 [4, 6, 9]。

第一份主食 $s=7$，未超预算，阈值 $\textit{remain}=12-7=5$。二分：$l=0$、$r=3$，中点 $mid=1$，arr[1]=6 > 5，于是 $r=1$；新区间 $[0,1)$，中点 $mid=0$，arr[0]=4 <= 5，于是 $l=1$；此时 $l=r=1$ 退出，返回 1。答案累加为 1。

第二份主食 $s=11$，未超预算，阈值 $\textit{remain}=1$。二分：$l=0$、$r=3$，$mid=1$，arr[1]=6 > 1，$r=1$；$mid=0$，arr[0]=4 > 1，$r=0$；$l=r=0$ 退出，返回 0。答案仍为 1。

第三份主食 $s=3$，阈值 $\textit{remain}=9$。二分：$l=0$、$r=3$，$mid=1$，arr[1]=6 <= 9，$l=2$；新区间 $[2,3)$，$mid=2$，arr[2]=9 <= 9，$l=3$；$l=r=3$ 退出，返回 3。答案累加为 4。

最终返回 4。手工枚举核对：$7+4=11$ 成立，$7+6=13$、$7+9=16$ 超标；$11+4=15$、$11+6=17$、$11+9=20$ 全部超标；$3+4=7$、$3+6=9$、$3+9=12$ 三种全部成立。合计 $1+0+3=4$，与二分结果一致。注意最后一组里 $3+9=12$ 恰好等于预算也算合法，这正是二分必须用 <= 而不是 < 的原因。

代码实现

// 累加并对 1e9+7 取模。
class Solution {
    private static final int MOD = 1_000_000_007;

    public int breakfastNumber(int[] staple, int[] drinks, int x) {
        Arrays.sort(drinks);
        long answer = 0;

        for (int s : staple) {
            if (s >= x) {
                continue;
            }
            int remain = x - s;
            int count = upperBound(drinks, remain);
            answer = (answer + count) % MOD;
        }

        return (int) answer;
    }

    private int upperBound(int[] arr, int target) {
        int l = 0;
        int r = arr.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (arr[m] <= target) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }
}

// 累加并对 1e9+7 取模。
func breakfastNumber(staple []int, drinks []int, x int) int {
    const mod = 1_000_000_007
    sort.Ints(drinks)
    answer := int64(0)

    for _, s := range staple {
        if s >= x {
            continue
        }
        remain := x - s
        count := upperBound(drinks, remain)
        answer = (answer + int64(count)) % mod
    }

    return int(answer)
}

func upperBound(arr []int, target int) int {
    l := 0
    r := len(arr)
    for l < r {
        m := l + (r-l)/2
        if arr[m] <= target {
            l = m + 1
        } else {
            r = m
        }
    }
    return l
}

复杂度分析

  • 时间复杂度：$O(m \log m + n \log m)$，其中 $n$ 是主食数量、$m$ 是饮料数量。凭据：排序饮料一次是 $O(m\log m)$；随后对每份主食做一次二分，每次二分把区间长度折半，轮数不超过 $\lceil\log_2 m\rceil$，共 $n$ 次。
  • 空间复杂度：$O(\log m)$，凭据：算法本身只用了累加器和几个下标变量；额外开销来自原地快速排序的递归栈，深度为对数级。若把排序视作输入预处理，则可认为是 $O(1)$。

关键点总结

  • 「统计满足条件的下标对数量」的通用套路是固定一侧、把另一侧变成范围计数。一旦条件能写成「另一侧的值不超过某个由当前元素决定的阈值」，排序加二分就直接可用。
  • upperBound 的返回值天然就是「不超过阈值的元素个数」，不需要再减一或加一。把这个等价关系记牢，能省掉大量边界推敲。
  • 二分务必固定一种区间约定并全程贯彻。本题用左闭右开：r 初始化为长度而非长度减一，循环条件是 l < r，收缩时写 r = m 而不是 r = m - 1，返回 l。四处细节必须匹配同一套语义。
  • 中点写成 l + (r - l) / 2 而不是 (l + r) / 2。虽然本题下标最大只有 $10^5$ 不会溢出，但这是应当固化的肌肉记忆。
  • 面试视角：题目一给出取模就要立刻反应「答案会超 32 位」。$10^5\times 10^5=10^{10}$ 这个乘积要能脱口而出，并明确说出用 64 位累加、逐步取模。
  • 面试视角：常见追问是「不排序能不能做」。因为价格上界只有 $10^5$，可以对饮料价格开桶计数再求前缀和，查询变成 $O(1)$，整体降到 $O(n+m+V)$；能给出这个值域相关的替代方案，说明对「排序换有序性」与「桶计数换有序性」两条路都有感觉。

易错点总结

  • 错误写法：用 32 位整数累加答案。用例两个数组各 $10^5$ 个元素且几乎全部搭配都合法 → 答案接近 $10^{10}$，int 早已回绕成负数，取模后仍然是错的。
  • 错误写法：整个循环跑完才取一次模。用例同上 → 若累加器是 64 位倒还撑得住，但一旦换成需要相乘的变体就会溢出；逐步取模是零成本的保险。
  • 错误写法：二分条件写成 arr[m] < target 却仍然返回 l。用例 drinks = [4, 6, 9]、阈值 9 → 返回的是第一个不小于 9 的位置 2，漏掉了价格恰好等于剩余预算的那份饮料，正确答案是 3。
  • 错误写法：把 r 初始化为 arr.length - 1 却保留 while (l < r) 和 return l。用例所有饮料价格都不超过阈值 → 返回值最大只能是 length - 1，永远数不到全部元素，结果系统性少一。
  • 错误写法：收缩右边界时写 r = m - 1。用例阈值恰好落在中点左侧 → 分界点本身被排除出区间，返回值偏小一位，属于典型的区间语义混用。
  • 错误写法：忘记先排序就直接二分。用例 drinks = [4, 9, 6] → 二分依赖有序性，在乱序数组上得到的下标毫无意义，结果随机偏差。
  • 错误写法：为了「对称」把两个数组都排序，然后仍然对每份主食做二分。用例任意输入 → 结果虽然正确但白白多花一次 $O(n\log n)$；更糟的是若因此误以为可以用双指针却没有正确同步指针方向，会直接算错。
  • 错误写法：对主食做剪枝时写成 if (s > x) continue，并假设 remain = 0 时二分一定返回 0。用例存在价格为 0 的饮料的变体 → 阈值为 0 时会数进这些饮料；本题价格都为正数所以侥幸不出错，但依赖题目隐含条件而不写清楚是隐患。
  • 错误写法：把「搭配数」理解成「不同价格组合数」并做去重。用例 staple = [3, 3]、drinks = [4]、x = 12 → 去重后得 1，而两份主食是两个不同的选择，正确答案是 2。
  • 错误写法：改用双指针时让两个指针都从左端出发同向移动。用例主食未排序 → 双指针解法要求主食升序、饮料降序（或反之）才能保证指针单调，方向搞错会漏计或重计；不确定时老老实实二分更稳。

相似题目

题目 难度 考察点
34. 在排序数组中查找元素的第一个和最后一个位置 中等 同时要写下界与上界两种二分
373. 查找和最小的 K 对数字 中等 同样是两数组配对，但要按和取前 $k$ 小
611. 有效三角形的个数 中等 排序后固定两边二分第三边，可对比双指针写法
704. 二分查找 简单 二分的最小骨架，用于校准区间语义
2300. 咒语和药水的成功对数 中等 阈值由除法得到，需注意向上取整的边界