企业官网建设流程全解析

wordpress建站 产品详情页,怎么让网站被收录,语音app开发公司,wordpress花园月亮(新卷,100分)- 生日礼物#xff08;Java JS Python C#xff09; 题目描述 小牛的孩子生日快要到了#xff0c;他打算给孩子买蛋糕和小礼物#xff0c;蛋糕和小礼物各买一个#xff0c;他的预算不超过x元。蛋糕cake和小礼物gift都有多种价位的可供选择…(新卷,100分)- 生日礼物Java JS Python C题目描述小牛的孩子生日快要到了他打算给孩子买蛋糕和小礼物蛋糕和小礼物各买一个他的预算不超过x元。蛋糕cake和小礼物gift都有多种价位的可供选择。请返回小牛共有多少种购买方案。输入描述第一行表示cake的单价以逗号分隔第二行表示gift的单价以逗号分隔第三行表示x预算输出描述输出数字表示购买方案的总数备注1 ≤ cake.length ≤ 10^51 ≤ gift.length ≤10^51 ≤ cake[i]gift[i] ≤ 10^51 ≤ X ≤ 2*10^5用例输入10,20,55,5,215输出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。题目解析本题可以使用二分查找解决。我的解题思路如下由于蛋糕和小礼物各买一个且总预算为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 种组合本题中如果存在多个相同的价格的蛋糕或者礼物比如gifts数组升序后为1,2,3,3,3,3,3,4而现在选择的蛋糕价格是3总预算是6那么gitfs最高价格可选3。因此我们期望二分查找返回gifts中价格3的位置是6即最后一个价格3的位置。而普通的二分查找无法找最后一个目标值的位置另外关于最终的购买方案可能会存在价位重复的组合那么是否需要去重可以看下用例1中第4种和第5种方案是不需要去重的。本题实际机考系统中存在20%的用例输入格式如下[10,20,5][5,5,2]15JS算法源码/* 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(%ld\n, 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 i0; igifts_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[mid1]) { return mid; } else { low mid 1; } } } return -low - 1; // 找不到则返回插入位置 }