LCP 18.早餐组合

​​题目来源：

        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;}
}

总结：

        无官方题解。

---