题目来源:
leetcode题目,网址:LCP 18. 早餐组合 - 力扣(LeetCode)
解题思路:
按序遍历饮料数组,二分查找符合要求 staple 中满足要求的最大值所在位置。最后返回所有*(最大位置+1)之和即可。
解题代码:
- class Solution {
- public int breakfastNumber(int[] staple, int[] drinks, int x) {
- int res=0;
- Arrays.sort(staple);
- Arrays.sort(drinks);
- int pre=staple.length-1;
- for(int i=0;i<drinks.length;i++){
- int thisPos=getPos(staple,pre,x-drinks[i]);
- if(thisPos==-1){
- break;
- }else{
- res+=thisPos+1;
- res=res%1000000007;
- pre=thisPos;
- }
- }
- return res;
- }
- public int getPos(int[] arr,int right,int max){
- if(arr[right]<=max){
- return right;
- }else if(arr[0]>max){
- return -1;
- }
- int left=0;
- int mid=left+(right-left)/2;
- while(!(arr[mid]<=max && arr[mid+1]>max)){
- mid=left+(right-left)/2;
- if(arr[mid]>max){
- right=mid-1;
- }else{
- left=mid+1;
- }
- }
- return mid;
-
- }
- }
总结:
无官方题解。