Python还能判断出早餐组合购买方案？吃早餐再也不愁不知道吃什

本文的文字及图片来源于网络,仅供学习、交流使用,不具有任何商业用途,版权归原作者所有,如有问题请及时联系我们以作处理

本篇文章来自腾讯云 作者：算法与编程之美

问题描述

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

注意：

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

提示：

1 <= staple.length <= 10^5

1 <= drinks.length <= 10^5

1 <= staple[i],drinks[i] <= 10^5

1 <= x <= 2*10^5

解决方案

首先可知买饮料的价格会小于等于总费用减去购买食物的支出额，所以可用两次二分查找进行解决；第一个二分查找得到买食物所能支出的最大金额（需保证所剩金额足够购买饮料）、第二个二分查找得到买饮料所能支出的最大金额。

代码如下：

from bisect import bisect_right
class Solution:
    def breakfastNumber(self, staple, drinks, x):
        s = 0
        staple.sort()
        drinks.sort()
        staple_len = bisect_right(staple, x - drinks[0])
        for food in staple[:staple_len]:
            i = bisect_right(drinks, x - food)
            s += i
        return s % 1000000007
if __name__ == '__main__':
    solution=Solution()
    a=solution.breakfastNumber()
    print(a)

结语

本题关键在于解决食物和饮料的搭配，需要灵活运用二分查找来分别得到购买食物和饮料所能支出的最大金额，第一次运用时需保证剩余资金足够购买饮料。