文章目录相关推荐阅读题目描述与示例题目描述输入描述输出描述示例输入输出解题思路代码PythonJavaCCNode JavaScriptGo时空复杂度华为OD算法/大厂面试高频题算法练习冲刺训练相关推荐阅读【华为OD机考正在更新】2025年双机位A卷真题【完全原创题解 | 详细考点分类 | 不断更新题目 | 六种主流语言PyJavaCppCJsGo】【华为OD机考】2025C2025B2024ED卷真题【完全原创题解 | 详细考点分类 | 不断更新题目】【华为OD笔试】双机位A2025C2025B2024ED卷真题机考套题汇总【真实反馈不断更新限时免费】【华为OD笔试】2024ED卷命题规律解读【分析500场OD笔试考点总结】【华为OD流程】性格测试选项注意事项】题目练习网址【贪心】双机位A-数字序列比大小题目描述与示例题目描述AB两个人玩一个数字比大小的游戏在游戏前两个人会拿到相同长度的两个数字序列两个数字序列不相同的且其中的数字是随机的。AB各自从数字序列中挑选出一个数字进行大小比较赢的人得1分输的人扣1分相等则各自的分数不变。 用过的数字需要丢弃。求A可能赢B的最大分数。输入描述输入数据的第1个数字表示数字序列的长度N后面紧跟着两个长度为N的数字序列。输出描述A可能赢B的最大分数示例输入3 4 8 10 3 6 4输出3解题思路这道题很明显是一道贪心结合双指针的题目。由于平局情况的出现本题难点在于我们如何地选择策略。很容易想到我们可以采取类似田忌赛马的策略为了使得A赢的尽可能多每次出现A中元素较小的时候我们总是选择这个较小的元素和B中尽可能大的数去分组。首先需要将两个数组各自排序方便考虑两个数组里的的最值情况。我们设置四个指针ia_leftia_rightib_leftib_right分别指向A、B数组中尚未比较过的元素的最小值和最大值。其初始化为ia_left0ib_left0ia_rightn-1ib_rightn-1如下图所示在一个while循环中比较A和B中尚未比较过元素的最小值即A[ia_left]和B[ib_left]。若A[ia_left] B[ib_left]。由于选择B中的其他数字可能会导致A[ia_left]无法获胜故选择该组进行比较A获胜。# A中最小值【大于】B中最小值的情况ifA[ia_left]B[ib_left]:ans1ia_left1ib_left1A[ia_left] B[ib_left]。由于此时A中最小值小于B中的任意一个元素我们不妨采取田忌赛马的策略让A[ia_left]和B[ib_right]进行分组B获胜。# A中最小值【小于】B中最小值的情况ifA[ia_left]B[ib_left]:ans-1ia_left1ib_right-1A[ia_left] B[ib_left]。这是最复杂的情况我们继续考虑A和B中尚未比较过元素的最大值即A[ia_right]和B[ib_right]情况。若A[ia_right] B[ib_right]即以下情况若此时令A[ia_left]和B[ib_right]分组由于A[ia_right]无论怎么配对都是必胜但A[ia_left]原本可以平局的配对现在却输了故不能采取这样的策略。故让A[ia_right]和B[ib_right]分组A[ia_right]获胜。# A中最小值【等于】B中最小值的情况ifA[ia_left]B[ib_left]:# A中最大值【大于】B中最大值的情况ifA[ia_right]B[ib_right]:ans1ia_right-1ib_right-1A[ia_right] B[ib_right]即以下情况由于此时B[ib_right]大于A中的任何一个元素A无论如何配对都必输故仍然维持着田忌赛马的策略令A[ia_left]和B[ib_right]分组B获胜。A[ia_right] B[ib_right]即以下情况此时固然可以令A[ia_left]和B[ib_left]、A[ai_right]和B[ib_right]两两分组但剩余元素的比较可能会让A的失利场次增多。以上图为例子如果选择A的1和B的1分组A的4和B的4分组那么剩下的A的2只能和B的3分组。A的结果是平2负1这不是最优解。最优解仍为A的1和B的4分组剩下就存在A的2和B的1分组A的4和B的3分组。A的结果是胜2负1这样才是最优解。故仍然应该选择A[ia_left]和B[ib_right]进行分组此时丢失的分数可能能够在A[ia_right]的其他配对中获取回来。显然这种情况可以和上一种情况A[ia_right] B[ib_right]合并在一起即# A中最小值【等于】B中最小值的情况ifA[ia_left]B[ib_left]:# A中最大值【小于等于】B中最大值的情况ifA[ia_right]B[ib_right]:# 只有当A中最小值小于B中最大值时A减分ifA[ia_left]B[ib_right]:ans-1ia_left1ib_right-1本题核心逻辑其实就是田忌赛马在A[ia_left]必定无法胜利的情况下无论是必输还是可能平局都尽量地让A[ia_left]和B[ib_right]配对。代码Python# 题目【贪心】2025A/双机位A-数字序列比大小# 分值200# 作者闭着眼睛学数理化# 算法贪心/双指针# 代码看不懂的地方请直接在群上提问nint(input())Alist(map(int,input().split()))Blist(map(int,input().split()))# 分别对A和B数组进行排序A.sort()B.sort()# 设置四个指针ia_left0ib_left0ia_rightn-1ib_rightn-1ans0# 进行循环# 由于每次判断A和B中的指针必定均移动一位# 故此处只需设置一个退出循环条件即可# 此处的循环不变量为ia_left小于等于ia_right# 即A中的每一个元素都必须遍历到whileia_leftia_right:# A中最小值【大于】B中最小值的情况ifA[ia_left]B[ib_left]:ans1ia_left1ib_left1# A中最小值【小于】B中最小值的情况elifA[ia_left]B[ib_left]:ans-1ia_left1ib_right-1# A中最小值【等于】B中最小值的情况elifA[ia_left]B[ib_left]:# A中最大值【大于】B中最大值的情况ifA[ia_right]B[ib_right]:ans1ia_right-1ib_right-1# A中最大值【小于等于】B中最大值的情况elifA[ia_right]B[ib_right]:ifA[ia_left]B[ib_right]:ans-1ia_left1ib_right-1print(ans)Javaimportjava.util.Arrays;importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){ScannerscannernewScanner(System.in);// 输入nintnscanner.nextInt();int[]Anewint[n];int[]Bnewint[n];// 输入数组Afor(inti0;in;i){A[i]scanner.nextInt();}// 输入数组Bfor(inti0;in;i){B[i]scanner.nextInt();}// 分别对A和B数组进行升序排序Arrays.sort(A);Arrays.sort(B);// 初始化四个指针intiaLeft0,ibLeft0;intiaRightn-1,ibRightn-1;intans0;// 循环直到A数组被完全遍历while(iaLeftiaRight){// A中最小值 B中最小值if(A[iaLeft]B[ibLeft]){ans;iaLeft;ibLeft;}// A中最小值 B中最小值elseif(A[iaLeft]B[ibLeft]){ans--;iaLeft;ibRight--;}// A中最小值 B中最小值else{// 比较A中最大值和B中最大值if(A[iaRight]B[ibRight]){ans;iaRight--;ibRight--;}else{if(A[iaLeft]B[ibRight]){ans--;}iaLeft;ibRight--;}}}// 输出最终得分System.out.println(ans);}}C#include iostream #include vector #include algorithm using namespace std; int main() { int n; cin n; vectorint A(n); vectorint B(n); // 输入数组A for (int i 0; i n; i) { cin A[i]; } // 输入数组B for (int i 0; i n; i) { cin B[i]; } // 对A和B数组进行升序排序 sort(A.begin(), A.end()); sort(B.begin(), B.end()); // 初始化四个指针 int iaLeft 0, ibLeft 0; int iaRight n - 1, ibRight n - 1; int ans 0; // 循环直到A数组被完全遍历 while (iaLeft iaRight) { // A中最小值 B中最小值 if (A[iaLeft] B[ibLeft]) { ans; iaLeft; ibLeft; } // A中最小值 B中最小值 else if (A[iaLeft] B[ibLeft]) { ans--; iaLeft; ibRight--; } // A中最小值 B中最小值 else { // 比较A中最大值和B中最大值 if (A[iaRight] B[ibRight]) { ans; iaRight--; ibRight--; } else { if (A[iaLeft] B[ibRight]) { ans--; } iaLeft; ibRight--; } } } // 输出最终得分 cout ans endl; return 0; }C#includestdio.h#includestdlib.h// 比较函数用于qsort进行升序排序intcmp(constvoid*a,constvoid*b){return(*(int*)a)-(*(int*)b);}intmain(){intn;scanf(%d,n);// 动态申请数组A和Bint*A(int*)malloc(n*sizeof(int));int*B(int*)malloc(n*sizeof(int));// 输入数组Afor(inti0;in;i){scanf(%d,A[i]);}// 输入数组Bfor(inti0;in;i){scanf(%d,B[i]);}// 对数组A和B进行升序排序qsort(A,n,sizeof(int),cmp);qsort(B,n,sizeof(int),cmp);// 初始化四个指针intiaLeft0,ibLeft0;intiaRightn-1,ibRightn-1;intans0;// 只要A数组还有元素未遍历就继续循环while(iaLeftiaRight){// A中最小值 B中最小值if(A[iaLeft]B[ibLeft]){ans;iaLeft;ibLeft;}// A中最小值 B中最小值elseif(A[iaLeft]B[ibLeft]){ans--;iaLeft;ibRight--;}// A中最小值 B中最小值else{// 比较A中最大值和B中最大值if(A[iaRight]B[ibRight]){ans;iaRight--;ibRight--;}else{if(A[iaLeft]B[ibRight]){ans--;}iaLeft;ibRight--;}}}// 输出最终得分printf(%d\n,ans);// 释放动态分配的内存free(A);free(B);return0;}Node JavaScriptconstreadlinerequire(readline);// 创建输入接口constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinputLines[];rl.on(line,(line){inputLines.push(line.trim());if(inputLines.length2*parseInt(inputLines[0])/parseInt(inputLines[0])1){main();rl.close();}});functionmain(){letnparseInt(inputLines[0]);// 输入nletAinputLines[1].split( ).map(Number);// 输入数组AletBinputLines[2].split( ).map(Number);// 输入数组B// 对A和B数组进行升序排序A.sort((a,b)a-b);B.sort((a,b)a-b);// 初始化四个指针letiaLeft0,ibLeft0;letiaRightn-1,ibRightn-1;letans0;// 循环直到A数组被完全遍历while(iaLeftiaRight){// A中最小值 B中最小值if(A[iaLeft]B[ibLeft]){ans;iaLeft;ibLeft;}// A中最小值 B中最小值elseif(A[iaLeft]B[ibLeft]){ans--;iaLeft;ibRight--;}// A中最小值 B中最小值else{// 比较A中最大值和B中最大值if(A[iaRight]B[ibRight]){ans;iaRight--;ibRight--;}else{if(A[iaLeft]B[ibRight]){ans--;}iaLeft;ibRight--;}}}// 输出最终得分console.log(ans);}Gopackagemainimport(fmtsort)funcmain(){varnintfmt.Scan(n)A:make([]int,n)B:make([]int,n)// 输入数组Afori:0;in;i{fmt.Scan(A[i])}// 输入数组Bfori:0;in;i{fmt.Scan(B[i])}// 分别对A和B数组进行升序排序sort.Ints(A)sort.Ints(B)// 初始化四个指针iaLeft,ibLeft:0,0iaRight,ibRight:n-1,n-1ans:0// 循环直到A数组被完全遍历foriaLeftiaRight{// A中最小值 B中最小值ifA[iaLeft]B[ibLeft]{ansiaLeftibLeft}elseifA[iaLeft]B[ibLeft]{// A中最小值 B中最小值ans--iaLeftibRight--}else{// A中最小值 B中最小值ifA[iaRight]B[ibRight]{// A中最大值 B中最大值ansiaRight--ibRight--}else{// A中最大值 B中最大值ifA[iaLeft]B[ibRight]{ans--}iaLeftibRight--}}}// 输出最终得分fmt.Println(ans)}时空复杂度时间复杂度O(NlogN)为排序所需的时间复杂度。在while循环双指针中两个列表中的每个元素只会经过一次双指针过程的时间复杂度为O(N)。空间复杂度O(1)。仅需四个指针若干常数变量华为OD算法/大厂面试高频题算法练习冲刺训练华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名目前已服务1000同学成功上岸课程讲师为全网200w粉丝编程博主吴师兄学算法以及小红书头部编程博主闭着眼睛学数理化90天陪伴式学习100直播课时300动画图解视频500LeetCode经典题500华为OD真题/大厂真题还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁