【二分查找】LCP 18. 早餐组合

?前言

?作者： 迷茫的启明星

学习路线
C语言从0到1
C++初阶
数据结构从0到1

?欢迎关注：?点赞?收藏✍️留言

?码字不易，你的?点赞?收藏❤️关注对我真的很重要，有问题可在评论区提出，感谢阅读！！！

持续更新中~

【二分查找】LCP 18. 早餐组合

在另一篇博客里讲过二分法的模板：
《二分法的模板讲解》

题目描述：

小扣在秋日市集选择了一家早餐摊位，一维整型数组 staple 中记录了每种主食的价格，一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料，且花费不超过 x 元。请返回小扣共有多少种购买方案。

注意：答案需要以 1e9 + 7 () 为底取模，如：计算初始结果为：，请返回 1

解题思路：

首先，我们需要对主食和饮料的价格进行排序。这样，我们可以在遍历主食价格的同时，使用二分查找法在有序的饮料价格中找到合适的饮料价格，使得主食和饮料的总价格不超过 x 元。

为了实现二分查找，我们需要定义左右指针 left 和 right，以及中间指针 mid。在每一次循环中，我们比较 drinks[mid] 与目标价格 target，即 x - staple[i]。如果 drinks[mid] 小于等于 target，说明饮料价格还有可能在左侧区间，所以我们将 left 指针更新为 mid + 1。否则，我们将 right 指针更新为 mid - 1。

当遍历完所有的主食价格后，我们将得到的购买方案数量 count 对 1e9 + 7 取模，最后返回 count。

代码实现：

class Solution {
public:
    int breakfastNumber(vector<int>& staple, vector<int>& drinks, int x) {
        sort(staple.begin(), staple.end());
        sort(drinks.begin(), drinks.end());
        int count = 0;
        for (int i = 0; i < staple.size(); ++i) {
            int target = x - staple[i];
            int left = 0, right = drinks.size() - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (drinks[mid] <= target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            count = (count + left) % ***;
        }
        return count;
    }
};

总结：

这道题目考察了排序和二分查找法在求解组合问题中的应用。通过将主食和饮料的价格排序，我们可以在 O(nlogn) 的时间复杂度内完成购买方案的查找。而二分查找法在这里起到了关键作用，使得我们可以在 O(logn) 的时间复杂度内找到合适的饮料价格。文章来源地址https://uudwc.com/A/9vdXV