【华为OD题库-046】生日礼物-java

题目

小牛的孩子生日快要到了，他打算给孩子买蛋糕和小礼物，蛋糕和小礼物各买一个，他的预算不超过x元。蛋糕cake和小礼物gift都有多种价位的可供选择。
请返回小牛共有多少种购买方案
输入描述
第一行表示cake的单价，以逗号分隔
第二行表示gift的单价，以逗号分隔
第三行表示x预算
输出描述
输出数字表示购买方案的总数
备注
1< cake.length ≤ 10^5
1 < gift.length <10^5。
1<cake[i], gift[i]<10^5。
1<X<2*10^5
示例1:
输入:
10,20,5
5,5,2
15
输出
6
解释:小牛有6种购买方案，所选蛋糕与所选礼物在数组中对应的下标分别是:
说明
第1种方案: cake [0] + gift [0]= 10+5=15
第2种方案: cake [0] + gift [1]= 10+5= 15;
第3种方案: cake [0] + gift [2]= 10+ 2=12;
第4种方案: cake [2] + gift [0]=5+5= 10;
第5种方案: cake [2] + gift [1]=5+5=10;
第6种方案: cake [2] + gift [2]=5+2=7.

思路

简单题，有以下思路

1. 暴力解法

将cases和gift按照从小到大排序，两层for循环即可求解：
当cakes[i] + gift[j] <= n，说明未超预算，结果+1
否则，超过了预算，因为已经从小到大排序，后续遍历只会使预算更大，所以应该break内层循环
继续外层循环
最后返回结果即可

2. 二分查找

因为题目要求买两种礼物，那么第一种礼物的价格应该小于x,即范围应该为：[1,x）
第二种的礼物价格为：x-第一种礼物的价值，此时右边应该取等，即范围为：[1,x-price1]
可以看到本题转化为了以下两个二分查找问题：

对于给定排序数组，找到最后一个小于target的位置
对于给定排序数组，找到最后一个不大于target的位置

因为两种要求二分法写法基本相同，所以可以融合到一个函数里去，详见题解

补充

二分法各种模板：

找第一个：

找到第一个大于等于x的数：

java">			mid=l+r>>1
            if (nums[mid] >= x) {
                r = mid;
            }  else {
 				l = mid+1;
            }

找到第一个大于x的数：

java">			mid=l+r>>1
			if (nums[mid] > x) {
                r = mid;
            }  else {
 				l = mid+1;
            }

找最后一个：

找到最后一个小于x的数：

java">			mid=l+r+1>>1
			if (nums[mid] < x) {
               l = mid;
            }  else {
 				r=mid-1;
            }

找到最后一个小于等于x的数：

java">			mid=l+r+1>>1
			if (nums[mid] <= x) {
               l = mid;
            }  else {
 				r=mid-1;
            }

题解

暴力查找

java">package hwod;

import java.util.Arrays;
import java.util.Scanner;

public class BirthDayGift {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] cakes = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        int[] gift = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        int n = sc.nextInt();
        System.out.println(birthDayGift(cakes, gift, n));

    }


    private static int birthDayGift(int[] cakes, int[] gift, int n) {
        Arrays.sort(cakes);
        Arrays.sort(gift);
        int res = 0;
        for (int i = 0; i < cakes.length; i++) {
            for (int j = 0; j < gift.length; j++) {
                if (cakes[i] + gift[j] <= n) res++;
                else break;
            }
        }
        return res;
    }
}

二分法

java">package hwod;

import java.util.Arrays;
import java.util.Scanner;

public class BirthDayGift {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] cakes = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        int[] gift = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        int n = sc.nextInt();
        System.out.println(birthDayGift(cakes, gift, n));

    }
    private static int birthDayGift(int[] cakes, int[] gift, int n) {
        Arrays.sort(cakes);
        Arrays.sort(gift);
        int res = 0;
        int idx = findGreatThanTarget(cakes, n, false);
        for (int i = 0; i <= idx; i++) {
            res += findGreatThanTarget(gift, n - cakes[i], true) + 1;
        }

        return res;
    }

    //flag取false：nums为从小到大排序的数组，找到最后一个小于target的位置
    //flag取true：nums为从小到大排序的数组，找到最后一个不大于target的位置
    private static int findGreatThanTarget(int[] nums, int target, boolean flag) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] > target) {
                r = mid - 1;
            } else if (nums[mid] < target) {
                l = mid;
            } else {
                if (flag) l = mid;
                else r = mid - 1;
            }
        }
        return l;
    }
}