Python|判断有几种早餐组合购买方案

问题描述小扣在秋日市集选择了一家早餐摊位，一维整型数组 staple 中记录了每种主食的价格，一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料，且花费不超过 x 元。请返回小扣共有多少种购买方案。注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1提示：1 <= staple.length <= 10^51 <= drinks.length <= 10^51 <= staple[i],drinks[i] <= 10^51 <= x <= 2*10^5解决方案首先可知买饮料的价格会小于等于总费用减去购买食物的支出额，所以可用两次二分查找进行解决；第一个二分查找得到买食物所能支出的最大金额（需保证所剩金额足够购买饮料）、第二个二分查找得到买饮料所能支出的最大金额。代码如下：from bisect import bisect_rightclass Solution:def breakfastNumber(self, staple, drinks, x):s = 0staple.sort()drinks.sort()staple_len = bisect_right(staple, x - drinks[0])for food in staple[:staple_len]:i = bisect_right(drinks, x - food)s += ireturn s % 1000000007if __name__ == '__main__':solution=Solution()a=solution.breakfastNumber()print(a)结语本题关键在于解决食物和饮料的搭配，需要灵活运用二分查找来分别得到购买食物和饮料所能支出的最大金额，第一次运用时需保证剩余资金足够购买饮料。实习编辑：欧洋责编 ：涂瀚鑫能力越强，责任越大。实事求是，严谨细致。（where2go团队）微信号：算法与编程之美