华为OD机试 - 生日礼物 - 二分查找（Java 2023 B卷 100分）

在这里插入图片描述

一、题目描述

小牛的孩子生日快要到了，他打算给孩子买蛋糕和小礼物，蛋糕和小礼物各买一个，他的预算不超过x元。蛋糕cake和小礼物gift都有多种价位的可供选择。

请返回小牛共有多少种购买方案。

二、输入描述

第一行表示cake的单价，以逗号分隔
第二行表示gift的单价，以逗号分隔
第三行表示X预算

三、输出描述

输出数字表示购买方案的总数。

备注：

1 < cake.length <= 10⁵；
1 < gift.length <= 10⁵；
1 < cake[i],gift[i] <= 10⁵；
1 < X <= 2 * 10⁵；

四、解题思路

这道题题意很简单，就是第一行选一个数、第二行选一个数，两数之和小于第三行的数，统计一下有多少种组合。

输入蛋糕cakes；
输入小礼物gifts；
输入预算X；
对礼物gifts进行升序排序；
遍历蛋糕集合cakes；
遍历礼物集合gifts，二分查找, 找到最大的满足位置；
返回的最大满足位置 + 1（因为下角标从0开始） = 在购买当前蛋糕时，可以买多少种小礼物；
输出数字表示购买方案的总数。

五、Java算法源码

java">public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    // 蛋糕cakes
    int[] cakes = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
    // 小礼物gifts
    int[] gifts = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
    // 预算
    int X = Integer.parseInt(sc.nextLine());

    // 对礼物gifts进行升序排序
    Arrays.sort(gifts);

    // 一共多少种购买方式
    int buyMethodSum = 0;
    // 遍历蛋糕集合cakes
    for (int cake : cakes) {
        if (X <= cake) {
            continue;
        }

        // 找到最大的满足位置
        int max = searchLast(gifts, X - cake);

        if (max >= 0) {
            // 返回的最大满足位置 + 1（因为下角标从0开始） = 在购买当前蛋糕时，可以买多少种小礼物
            buyMethodSum += max + 1;
        } else {
            max = -max - 1;
            buyMethodSum += max;
        }
    }

    System.out.println(buyMethodSum);
}

/**
 * 遍历礼物集合gifts，二分查找, 找到最大的满足位置
 *
 * @param gifts 礼物集合
 * @param target 预算 - 蛋糕
 * @return 最大的满足位置
 */
public static int searchLast(int[] gifts, int target) {
    int left = 0;
    int right = gifts.length - 1;

    while (left <= right) {
        // 二分查找
        int mid = (left + right) >> 1;

        // 如果中间数 大于 剩余预算
        if (gifts[mid] > target) {
            right = mid - 1;
        } else if (gifts[mid] < target) {// 如果中间数 小于 剩余预算
            left = mid + 1;
        } else {// 如果中间数 等于 剩余预算
            /**
             * 如果中间位置最后一个（遍历光了）
             * 或者
             * 中间位置的数 不等于 中间位置的下一个数（因为要求找到最大的满足位置，挨着的数不相等，相等的话要取下一个位置）
             * 直接返回mid位置
             */
            if (mid == gifts.length - 1 || gifts[mid] != gifts[mid + 1]) {
                return mid;
            } else {//否则继续向右二分查找
                left = mid + 1;
            }
        }
    }

    return -left - 1;
}