华为OD机考算法题：生日礼物

题目部分


题目	生日礼物
难度	易
题目说明	小牛的孩子生日快要到了，他打算给孩子买蛋糕和小礼物，蛋糕和小礼物各买一个，他的预算不超过x元。蛋糕 cake 和小礼物 gift 都有多种价位的可供选择。
输入描述	第一行表示cake的单价，以逗号分隔。第二行表示gift的单价，以逗号分隔。第三行表示 x 预算。
输出描述	输出数字表示购买方案的总数。
补充说明	1 ≤ cake.length ≤ $10^{5}$ 1 ≤ gift.length ≤ $10^{5}$ 1 ≤ cake[], gift[] ≤ $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。

解读与分析

题目解读：

给定 2 组数据，在两组数据中各取 1 个，使 2 个数字之和不高于指定值 x。

分析与思路：

如果逐个遍历两组数字中每一种组合，时间复杂度为 O( $n^{2}$ )。由于 cake、gift 的最大长度为 $10^{5}$ ，当它们长度较大时，性能会变得很差，我们有更好的方法。

实现如下：
1. 对 cake、gift 进行排序，从大到小。
2. 对 cake 进行二分查找，从 cake 中找到值小于 x 的最大值所对应的下标，设为 minCake。此时，计算出cake 中可能买的 cake 下标范围是 [ minCake, cake.length - 1]。对处于下标范围的 cake 遍历（假设当前正遍历到的下标为 i），进行步骤 3 操作。
3. 如步骤 2，假设当前的 cake 是 cake[i]，那么所能购买的 gift 最大价格为 x - cake[i]，设为 giftMaxValue。使用二分查找，找到价格不高于 giftMaxValue 的最大值，设下标为 j，那么 gift 的下标可选范围是 [ j, gift.length -1 ]。即意味着当选择 cake[i] 时，gift 的可选个数是 gift.length - j。
4. 继续遍历下一个 cake，即下一个 i，如步骤 3 中，重新计算 giftMaxValue，此时的 giftMaxValue 一定大于前一个计算出来的 giftMaxValue，即意味着这一轮中 gift 下标的 j 的范围一定在 0 和上一轮计算出来的 j 之间，对 [ 0, 上一轮计算的 j ] 进行二分查找，找到不大于 giftMaxValue 的最大值（即最下小标），即计算出选择当前 cake 时，gift 的可选个数。
5. 继续进行步骤 4，直至遍历完所有的 cake，最终所有可选个数之和，即为购买方案总数。

这种方案的时间复杂度为O(nlogn)，空间复杂度O(n)。

代码实现

Java代码

import java.util.Arrays;
import java.util.Scanner;
import java.util.Comparator;/*** 生日礼物* * @since 2023.10.31* @version 0.1* @author Frank**/
public class BirthdayGift {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();String[] strNumber = input.split(",");Integer[] cakes = new Integer[strNumber.length];for (int i = 0; i < strNumber.length; i++) {cakes[i] = Integer.parseInt(strNumber[i]);}input = sc.nextLine();strNumber = input.split(",");Integer[] gifts = new Integer[strNumber.length];for (int i = 0; i < strNumber.length; i++) {gifts[i] = Integer.parseInt(strNumber[i]);}input = sc.nextLine();int x = Integer.parseInt(input);processBirthdayGift(cakes, gifts, x);}}private static void processBirthdayGift(Integer[] cakes, Integer[] gifts, int x) {	// 从大到小排序Comparator<Integer> comp = new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}};Arrays.sort( cakes, comp );Arrays.sort( gifts, comp );int cakesFromIndex = findMaxValueIndex( x - 1, cakes.length - 1, cakes );int sum = 0;int highIndex = gifts.length - 1;for( int i = cakesFromIndex; i < cakes.length; i ++ ){int giftMaxValue = x - cakes[i];highIndex = findMaxValueIndex( giftMaxValue, highIndex, gifts );sum += ( gifts.length - highIndex ) ;}	System.out.println( sum );}private static int findMaxValueIndex( int maxValue, int highIndex, Integer[] srcArr ){// 已排序从大到小的数组，取值范围在 [0, fromIndex]int low = 0;int high = highIndex;int mid = ( low + high ) / 2;while( low <= high ){mid = ( low + high ) / 2;if( maxValue == srcArr[mid] ){// 相等，还需判断所有相等的情况while( mid >= 1 && srcArr[mid - 1 ] == srcArr[mid]){mid --;}return mid;}else if( maxValue > srcArr[mid] ){high = mid - 1;}else{low = mid + 1;}}// 此时 low > highif( high < 0 ){return 0;}if( srcArr[ high ] < maxValue ){return high;}if( srcArr[low] < maxValue ){return low;}if( low + 1 <= srcArr.length -1 ){return low + 1;}else{return srcArr.length -1;}}
}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {var strNumber = line.split(",");var cakes = new Array();for (var i = 0; i < strNumber.length; i++) {cakes[i] = parseInt(strNumber[i]);}line = await readline();var strNumber = line.split(",");var gifts = new Array();for (var i = 0; i < strNumber.length; i++) {gifts[i] = parseInt(strNumber[i]);}line = await readline();var x = parseInt(line);processBirthdayGift(cakes, gifts, x);}
}();function processBirthdayGift(cakes, gifts, x) {// 从大到小排序var comp = function( a, b) {return b - a;        };cakes.sort( comp );gifts.sort( comp );var cakesFromIndex = findMaxValueIndex( x - 1, cakes.length - 1, cakes );var sum = 0;var highIndex = gifts.length - 1;for( var i = cakesFromIndex; i < cakes.length; i ++ ){var giftMaxValue = x - cakes[i];highIndex = findMaxValueIndex( giftMaxValue, highIndex, gifts );sum += ( gifts.length - highIndex ) ;}   console.log( sum );
}function findMaxValueIndex(maxValue, highIndex, srcArr) {// 已排序从大到小的数组，取值范围在 [0, fromIndex]var low = 0;var high = highIndex;var mid = parseInt( (low + high) / 2 );while (low <= high) {mid = parseInt( (low + high) / 2 );if (maxValue == srcArr[mid]) {// 相等，还需判断所有相等的情况while (mid >= 1 && srcArr[mid - 1] == srcArr[mid]) {mid--;}return mid;} else if (maxValue > srcArr[mid]) {high = mid - 1;} else {low = mid + 1;}}// 此时 low > highif (high < 0) {return 0;}if (srcArr[high] < maxValue) {return high;}if (srcArr[low] < maxValue) {return low;}// should never come hereif (low + 1 <= srcArr.length - 1) {return low + 1;} else {return srcArr.length - 1;}
}

(完)

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/176341.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！