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)

结语

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

实习编辑：欧洋

责编 ：涂瀚鑫

能力越强，责任越大。

实事求是，严谨细致。

（where2go团队）

微信号：算法与编程之美