企业官网建设流程全解析

相关推荐阅读

• 【华为OD机考正在更新】2025年双机位A卷真题【完全原创题解 | 详细考点分类 | 不断更新题目 | 六种主流语言Py+Java+Cpp+C+Js+Go】
• 【华为OD机考】2025C+2025B+2024E+D卷真题【完全原创题解 | 详细考点分类 | 不断更新题目】
• 【华为OD笔试】双机位A+2025C+2025B+2024E+D卷真题机考套题汇总【真实反馈，不断更新，限时免费】
• 【华为OD笔试】2024E+D卷命题规律解读【分析500+场OD笔试考点总结】
• 【华为OD流程】性格测试选项+注意事项】

题目练习网址：【贪心】双机位A-数字序列比大小

题目描述与示例

题目描述

A，B两个人玩一个数字比大小的游戏，在游戏前，两个人会拿到相同长度的两个数字序列，两个数字序列不相同的，且其中的数字是随机的。

A，B各自从数字序列中挑选出一个数字进行大小比较，赢的人得1分，输的人扣1分，相等则各自的分数不变。 用过的数字需要丢弃。

求A可能赢B的最大分数。

输入描述

输入数据的第1个数字表示数字序列的长度N，后面紧跟着两个长度为N的数字序列。

输出描述

A可能赢B的最大分数

示例

输入

3 4 8 10 3 6 4

输出

3

解题思路

这道题很明显是一道贪心结合双指针的题目。由于平局情况的出现，本题难点在于我们如何地选择策略。

很容易想到我们可以采取类似田忌赛马的策略：为了使得A赢的尽可能多，每次出现A中元素较小的时候，我们总是选择这个较小的元素和B中尽可能大的数去分组。

首先需要将两个数组各自排序，方便考虑两个数组里的的最值情况。

我们设置四个指针ia_left，ia_right，ib_left，ib_right，分别指向A、B数组中尚未比较过的元素的最小值和最大值。其初始化为

ia_left=0ib_left=0ia_right=n-1ib_right=n-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]:ans+=1ia_left+=1ib_left+=1

• A[ia_left] < B[ib_left]。由于此时A中最小值小于B中的任意一个元素，我们不妨采取田忌赛马的策略，让A[ia_left]和B[ib_right]进行分组，B获胜。

# A中最小值【小于】B中最小值的情况ifA[ia_left]<B[ib_left]:ans-=1ia_left+=1ib_right-=1

• A[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]:ans+=1ia_right-=1ib_right-=1

  • A[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_left+=1ib_right-=1

本题核心逻辑其实就是田忌赛马，在A[ia_left]必定无法胜利的情况下（无论是必输还是可能平局），都尽量地让A[ia_left]和B[ib_right]配对。

代码

Python

# 题目：【贪心】2025A/双机位A-数字序列比大小# 分值：200# 作者：闭着眼睛学数理化# 算法：贪心/双指针# 代码看不懂的地方，请直接在群上提问n=int(input())A=list(map(int,input().split()))B=list(map(int,input().split()))# 分别对A和B数组进行排序A.sort()B.sort()# 设置四个指针ia_left=0ib_left=0ia_right=n-1ib_right=n-1ans=0# 进行循环，# 由于每次判断，A和B中的指针必定均移动一位# 故此处只需设置一个退出循环条件即可# 此处的循环不变量为ia_left小于等于ia_right# 即A中的每一个元素都必须遍历到whileia_left<=ia_right:# A中最小值【大于】B中最小值的情况ifA[ia_left]>B[ib_left]:ans+=1ia_left+=1ib_left+=1# A中最小值【小于】B中最小值的情况elifA[ia_left]<B[ib_left]:ans-=1ia_left+=1ib_right-=1# A中最小值【等于】B中最小值的情况elifA[ia_left]==B[ib_left]:# A中最大值【大于】B中最大值的情况ifA[ia_right]>B[ib_right]:ans+=1ia_right-=1ib_right-=1# A中最大值【小于等于】B中最大值的情况elifA[ia_right]<=B[ib_right]:ifA[ia_left]<B[ib_right]:ans-=1ia_left+=1ib_right-=1print(ans)

Java

importjava.util.Arrays;importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);// 输入nintn=scanner.nextInt();int[]A=newint[n];int[]B=newint[n];// 输入数组Afor(inti=0;i<n;i++){A[i]=scanner.nextInt();}// 输入数组Bfor(inti=0;i<n;i++){B[i]=scanner.nextInt();}// 分别对A和B数组进行升序排序Arrays.sort(A);Arrays.sort(B);// 初始化四个指针intiaLeft=0,ibLeft=0;intiaRight=n-1,ibRight=n-1;intans=0;// 循环直到A数组被完全遍历while(iaLeft<=iaRight){// 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; vector<int> A(n); vector<int> 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

#include<stdio.h>#include<stdlib.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(inti=0;i<n;i++){scanf("%d",&A[i]);}// 输入数组Bfor(inti=0;i<n;i++){scanf("%d",&B[i]);}// 对数组A和B进行升序排序qsort(A,n,sizeof(int),cmp);qsort(B,n,sizeof(int),cmp);// 初始化四个指针intiaLeft=0,ibLeft=0;intiaRight=n-1,ibRight=n-1;intans=0;// 只要A数组还有元素未遍历，就继续循环while(iaLeft<=iaRight){// 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 JavaScript

constreadline=require('readline');// 创建输入接口constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinputLines=[];rl.on('line',(line)=>{inputLines.push(line.trim());if(inputLines.length===2*parseInt(inputLines[0])/parseInt(inputLines[0])+1){main();rl.close();}});functionmain(){letn=parseInt(inputLines[0]);// 输入nletA=inputLines[1].split(' ').map(Number);// 输入数组AletB=inputLines[2].split(' ').map(Number);// 输入数组B// 对A和B数组进行升序排序A.sort((a,b)=>a-b);B.sort((a,b)=>a-b);// 初始化四个指针letiaLeft=0,ibLeft=0;letiaRight=n-1,ibRight=n-1;letans=0;// 循环直到A数组被完全遍历while(iaLeft<=iaRight){// 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);}

Go

packagemainimport("fmt""sort")funcmain(){varnintfmt.Scan(&n)A:=make([]int,n)B:=make([]int,n)// 输入数组Afori:=0;i<n;i++{fmt.Scan(&A[i])}// 输入数组Bfori:=0;i<n;i++{fmt.Scan(&B[i])}// 分别对A和B数组进行升序排序sort.Ints(A)sort.Ints(B)// 初始化四个指针iaLeft,ibLeft:=0,0iaRight,ibRight:=n-1,n-1ans:=0// 循环直到A数组被完全遍历foriaLeft<=iaRight{// A中最小值 > B中最小值ifA[iaLeft]>B[ibLeft]{ans++iaLeft++ibLeft++}elseifA[iaLeft]<B[ibLeft]{// A中最小值 < B中最小值ans--iaLeft++ibRight--}else{// A中最小值 == B中最小值ifA[iaRight]>B[ibRight]{// A中最大值 > B中最大值ans++iaRight--ibRight--}else{// A中最大值 <= B中最大值ifA[iaLeft]<B[ibRight]{ans--}iaLeft++ibRight--}}}// 输出最终得分fmt.Println(ans)}

时空复杂度

时间复杂度：O(NlogN)，为排序所需的时间复杂度。在while循环双指针中，两个列表中的每个元素只会经过一次，双指针过程的时间复杂度为O(N)。

空间复杂度：O(1)。仅需四个指针，若干常数变量

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务1000+同学成功上岸！

• 课程讲师为全网200w+粉丝编程博主@吴师兄学算法以及小红书头部编程博主@闭着眼睛学数理化

• 90+天陪伴式学习，100+直播课时，300+动画图解视频，500+LeetCode经典题，500+华为OD真题/大厂真题，还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁