(B卷,100分)- 生日礼物（Java & JS & Python & C）

题目描述

小牛的孩子生日快要到了，他打算给孩子买蛋糕和小礼物，蛋糕和小礼物各买一个，他的预算不超过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

用例

题目解析

本题可以使用二分查找解决。

我的解题思路如下：

由于蛋糕和小礼物各买一个，且总预算为x。

因此，假设我们先买了蛋糕花了cake元，那么能用于买到的小礼物的最高价格就已经确定了，为x – cake元。因此只要<=x – cake元的小礼物，都可以可以cake元的蛋糕组合。

为了避免花费O(n)时间在gifts中找<=x – cake元的小礼物，我们可以将gifts进行升序，然后通过二分查找x-cake元在升序后的gitfs中的位置

二分查找目标值target在有序数组nums中的位置，有两种情况：

• nums中存在target，则二分查找最终会返回target在nums中的位置
• nums中不存在target，则二分查找会返回target在nums中的有序插入位置

关于这两个位置的实现，可以看下面博客中二分查找部分：

如果gifts进行升序后，二分查找x-cake元的位置 i ：

• i 是目标位置，则可以产生 i + 1 种组合
• i 是有序插入位置，则 i = -i -1，即需要先变为有序插入位置，而有序插入位置的必然 gitfs[i] >  x – cake，因此只能产生 i 种组合

2023.06.12

本题中如果存在多个相同的价格的蛋糕或者礼物，

比如gifts数组升序后为：1,2,3,3,3,3,3,4

而现在选择的蛋糕价格是3，总预算是6，那么gitfs最高价格可选3。

因此，我们期望二分查找返回gifts中价格3的位置是6，即最后一个价格3的位置。

而普通的二分查找，无法找最后一个目标值的位置，此时的解决思路是：

LeetCode – 34 在排序数组中查找元素的第一个和最后一个位置_伏城之外的博客-CSDN博客

另外，关于最终的购买方案，可能会存在价位重复的组合，那么是否需要去重？

可以看下用例1中，第4种和第5种方案，是不需要去重的。

2023.08.29

根据考友实际考试反馈，本题实际机考系统中，存在20%的用例输入格式如下：

[10,20,5]
[5,5,2]
15

即第一行，第二行输入多了一个左右方括号

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 3) {
    // 这里replaceAll的原因是：有考友反馈实际考试存在20%的用例输入类似于 [10,20,5] 这种
    const cakes = lines[0]
      .replaceAll(/[[]]/g, "")
      .split(",")
      .map(Number);
    const gifts = lines[1]
      .replaceAll(/[[]]/g, "")
      .split(",")
      .map(Number);
    const x = parseInt(lines[2]);

    console.log(getResult(cakes, gifts, x));

    lines.length = 0;
  }
});

function getResult(cakes, gifts, x) {
  cakes.sort((a, b) => a - b);

  let ans = 0;
  for (let gift of gifts) {
    if (x <= gift) continue;

    const maxCake = x - gift;
    let i = searchLast(cakes, maxCake);

    if (i >= 0) {
      ans += i + 1;
    } else {
      i = -i - 1;
      ans += i;
    }
  }

  return ans;
}

function searchLast(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = (low + high) >> 1;
    const midVal = arr[mid];

    if (midVal > target) {
      high = mid - 1;
    } else if (midVal < target) {
      low = mid + 1;
    } else {
      // 向右延伸判断，mid是否为target数域的右边界，即最后一次出现的位置
      if (mid == arr.length - 1 || arr[mid] != arr[mid + 1]) {
        return mid;
      } else {
        low = mid + 1;
      }
    }
  }

  return -low - 1; // 找不到则返回插入位置
}

Java算法源码

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

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    // 这里replaceAll的原因是：有考友反馈实际考试存在20%的用例输入类似于 [10,20,5] 这种
    int[] cakes =
        Arrays.stream(sc.nextLine().replaceAll("[\[\]]", "").split(","))
            .mapToInt(Integer::parseInt)
            .toArray();

    int[] gifts =
        Arrays.stream(sc.nextLine().replaceAll("[\[\]]", "").split(","))
            .mapToInt(Integer::parseInt)
            .toArray();
    int x = Integer.parseInt(sc.nextLine());

    System.out.println(getResult(cakes, gifts, x));
  }

  public static long getResult(int[] cakes, int[] gifts, int x) {
    Arrays.sort(cakes);

    long ans = 0;
    for (int gift : gifts) {
      if (x <= gift) continue;

      int maxCake = x - gift;
      int i = searchLast(cakes, maxCake);

      if (i >= 0) {
        ans += i + 1;
      } else {
        i = -i - 1;
        ans += i;
      }
    }

    return ans;
  }

  public static int searchLast(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high) {
      int mid = (low + high) >> 1;
      int midVal = arr[mid];

      if (midVal > target) {
        high = mid - 1;
      } else if (midVal < target) {
        low = mid + 1;
      } else {
        // 向右延伸判断，mid是否为target数域的右边界，即最后一次出现的位置
        if (mid == arr.length - 1 || arr[mid] != arr[mid + 1]) {
          return mid;
        } else {
          low = mid + 1;
        }
      }
    }

    return -low - 1; // 找不到则返回插入位置
  }
}

Python算法源码

import re

# 输入获取
# 这里re.sub的原因是：有考友反馈实际考试存在20%的用例输入类似于 [10,20,5] 这种
cakes = list(map(int, re.sub(r"[[]]", "", input()).split(",")))
gifts = list(map(int, re.sub(r"[[]]", "", input()).split(",")))
x = int(input())


def searchLast(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) >> 1
        midVal = arr[mid]

        if midVal > target:
            high = mid - 1
        elif midVal < target:
            low = mid + 1
        else:
            if mid == len(arr) - 1 or arr[mid] != arr[mid + 1]:
                return mid
            else:
                low = mid + 1

    return -low - 1


# 算法入口
def getResult():
    cakes.sort()

    ans = 0
    for gift in gifts:
        if x <= gift:
            continue

        maxCake = x - gift
        i = searchLast(cakes, maxCake)

        if i >= 0:
            ans += i + 1
        else:
            i = -i - 1
            ans += i

    return ans


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100000

long getResult(int* cakes, int cakes_size, int* gifts, int gifts_size, int x);
int cmp(const void* a, const void* b);
int searchLast(int* arr, int arr_size, int target);

int main()
{
// 有考友反馈实际考试存在20%的用例输入类似于 [10,20,5] 这种
// 因此输入获取时需要注意处理这种特殊输入情况
int cakes[MAX_SIZE];
int cakes_size = 0;
while(scanf("%d", &cakes[cakes_size]) || scanf("[%d", &cakes[cakes_size])) {
cakes_size++;
if(getchar() != ',') break;
}

int gifts[MAX_SIZE];
int gifts_size = 0;
while(scanf("%d", &gifts[gifts_size]) || scanf("[%d", &gifts[gifts_size])) {
gifts_size++;
if(getchar() != ',') break;
}

int x;
scanf("%d", &x);

printf("%ldn", getResult(cakes, cakes_size, gifts, gifts_size, x));

return 0;
}

long getResult(int* cakes, int cakes_size, int* gifts, int gifts_size, int x)
{
qsort(cakes, cakes_size, sizeof(int), cmp);

long ans = 0;
for(int i=0; i<gifts_size; i++) {
int gift = gifts[i];

if(x <= gift) continue;

int maxCake = x - gift;
int i = searchLast(cakes, cakes_size, maxCake);

if(i >= 0) {
ans += i + 1;
} else {
i = -i - 1;
ans += i;
}
}

return ans;
}

int cmp(const void* a, const void* b)
{
return *((int*) a) - *((int*) b);
}

int searchLast(int* arr, int arr_size, int target)
{
int low = 0;
int high = arr_size - 1;

while(low <= high) {
int mid = (low + high) >> 1;
int midVal = arr[mid];

if(midVal > target) {
high = mid - 1;
} else if(midVal < target) {
low = mid + 1;
} else {
// 向右延伸判断，mid是否为target数域的右边界，即最后一次出现的位置
if(mid == arr_size - 1 || arr[mid] != arr[mid+1]) {
return mid;
} else {
low = mid + 1;
}
}
}

return -low - 1; // 找不到则返回插入位置
}