LeetCode LCP 18. 早餐组合

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

题目描述

✅ LCP 18. 早餐组合

image-20260928230204086

image-20260928230204088

题意分析

从主食数组和饮料数组中各选一个下标，使总价不超过预算 x，统计所有搭配数，并对 1_000_000_007 取模。相同价格但下标不同，仍是不同选择；主食和饮料价格都为正数。

解法：排序 + 二分计数

核心思路

[!blue]

固定一份主食，价格为 s，饮料价格就必须不大于 remain = x - s。只把饮料数组排序后，所有合法饮料恰好构成一个前缀，所以只需求出这个前缀的长度，无需逐一枚举配对。

二分查找第一个严格大于 remain 的位置，记为 count。下标 0..count-1 都合法，后面都不合法，因此这个位置本身就是合法饮料数量。所有饮料都超预算时返回 0，所有饮料都合法时返回数组长度，两种边界无需额外处理。

二分维护 [0, l) 已知合法、[r, m) 已知不合法，中间 [l, r) 待判断。若中点价格 <= remain，它和左侧都合法，令 l = mid + 1；否则它及右侧都不合法，令 r = mid。结束时 l = r，正好停在两段的分界。

对每份主食独立统计并相加。每个下标对只会在枚举它的主食时计入一次，既不会重复也不会遗漏；重复价格必须保留，才能保留全部商品选择。

解题步骤

  • 将 drinks 升序排序，初始化答案为 0。
  • 遍历每份主食价格 s。若 s >= x，由于饮料价格至少为 1，这份主食没有合法搭配，直接跳过。
  • 否则计算剩余预算，使用半开区间二分求第一个价格大于它的位置。
  • 将返回的位置加入答案，每次累加后取模。取模与加法兼容，得到的结果等价于最后对总搭配数取模。

代码实现

// 累加并对 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;
    }
}

import "sort"

// 累加并对 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
}

复杂度分析

设主食数量为 n、饮料数量为 m。

  • 时间复杂度：$O((m+n)\log(m+1))$。饮料排序后，对每份主食执行一次二分查找。
  • 空间复杂度：二分查询本身为 $O(1)$；计入库排序，Java 辅助空间保守记为 $O(m)$，Go 排序栈为 $O(\log(m+1))$。

关键点总结

[!green]

  • 固定主食后，问题只剩统计价格不超过某个阈值的饮料数。
  • 总价等于预算仍合法，所以边界是第一个严格大于剩余预算的位置。
  • 只需给饮料排序，主食按输入顺序逐个处理即可。

易错点总结

[!yellow]

  • 查找第一个大于等于阈值的位置，会漏掉恰好用完预算的饮料。
  • 二分返回的是合法前缀长度，不要再减 1，也不要把它当成最后一个合法下标。
  • 不能去重价格，否则会把不同商品下标对应的方案合并。
  • 主食没有排序，遇到一份超预算时只能跳过它，不能终止后续枚举。

相似题目

题目 难度 关联与区别
2300. 咒语和药水的成功对数 中等 同样从两数组各选一项计数，本题按总价不超过预算，原题按乘积达到阈值，比较方向与运算不同。
1099. 小于 K 的两数之和 简单 原题找严格小于阈值的最大两数和，本题允许等于预算且要计入全部下标组合。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/79124591
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！