华为OD机试双机位C卷 - 结对编程 (C++ Python JAVA JS GO)-编程阁

结对编程

2025华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 200分题型

华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录｜机考题库 + 算法考点详解

题目描述

某部门计划通过结队编程来进行项目开发，已知该部门有 N 名员工，每个员工有独一无二的职级，每三个员工形成一个小组进行结队编程，结队分组规则如下：

从部门中选出序号分别为 i、j、k 的3名员工，他们的职级分别为 level[i]，level[j]，level[k]，结队小组满足 level[i] < level[j] < level[k] 或者 level[i] > level[j] > level[k]，其中 0 ≤ i < j < k < n。

请你按上述条件计算可能组合的小组数量。同一员工可以参加多个小组。

输入描述

第一行输入：员工总数 n

第二行输入：按序号依次排列的员工的职级 level，中间用空格隔开

备注

1 <= n <= 6000
1 <= level[i] <= 10^5

输出描述

可能结队的小组数量

用例1

输入

4 1 2 3 4

输出

说明

可能结队成的组合(1,2,3)、(1,2,4)、(1,3,4)、(2,3,4)

用例2

输入

3 5 4 7

输出

题解

思路：逻辑分析 + 树状数组

这道题可以枚举中间j，当枚举到nums[j], 它可以组成为左侧小于它的数量 * 右侧大于它的数量 + 左侧大于的数量 * 右侧小于它的数量分别对应level[i] < level[j] < level[k]的情况和level[i] > level[j] > level[k]的情况相加。
所以根据1的分析得来，只需要累加所有位置作为中间节点合法组合情况就能得到结果。那现在问题就转换为如何统计左侧小于它的数量, 右侧大于它的数量,左侧大于的数量,右侧小于它的数量, 然后由于这道题n <= 6000如果直接使用暴力统计很可能超时，接下来为了快速统计引入树状数组前缀和方式进行优化，达到快速得到上面所需要的四种数量。如果不了解树状数组，可以搜索去学习一下
开始定义trie1[max(nums) + 1], trie2[max(nums) + 1], 其中trie1[i], trie2[i]可以简单理解为记录小于等于i的数量。其中max(nums)表示最高职级大小
对于统计左侧比nums[j]大/小的数量比较好做，只需要在枚举 j 的过程中，将nums[j]添加到树状数组tri1即可。具体值为
- 左侧小于nums[j]的数量:tri1[nums[j] - 1]
- 左侧大于nums[j]的数量:tri1[max(nums)] - trie1[nums[j]], 前缀和思想。
那么对于需要统计右侧比nums[j]小/大的数量，凭tri1无法做到，所以引入trie2树状数组，初始先将所有nums加入到trie2中，然后在在枚举 j 的过程中，将nums[j]移除到树状数组tri2即可（其实就相当于把整个数组分为两部分，全部 - 左边 = 右边），然后就非常好统计，具体值为
- 右侧小于nums[j]的数量为:tri2[nums[j] - 1]
- 右侧大于nums[j]的数量为:tri2[max(nums[j])] - tri2[num[j]]
按照上面具体逻辑处理就能得到最终结果，然后输出即可。

c++

#include <algorithm> #include <cmath> #include <iostream> #include <map> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int N = 1e5 + 10; // 树状数组 更新值 // 参数：tree 数组，index 更新的位置，delta 增加的值 void update(vector<int> &tree, int index, int delta) { int n = (int)tree.size() - 1; while (index <= n) { tree[index] += delta; // 更新当前位置的值 index += index & (-index); // 跳到所有包含这个位置的父区间 } } // 树状数组 查询区间和 // 参数：tree 数组，index 查询的前缀位置 // 返回值：从1到index的区间和 int query(const vector<int> &tree, int index) { int res = 0; while (index > 0) { res += tree[index]; // 累加当前节点值 index -= index & (-index); // 跳到上一个区间的父区间 } return res; } int main() { int n; cin >> n; vector<int> nums(n); int maxv = 0; for (int i = 0; i < n; i++) { cin >> nums[i]; maxv = max(maxv, nums[i]); } // 树状数组 vector<int> tri1(maxv + 1), tri2(maxv + 1); // tri2 先放所有元素 for (int x : nums) { update(tri2, x, 1); } long long ans = 0; // 枚举中间值j for (int i = 0; i < n; i++) { int num = nums[i]; // 当前元素从右侧移除 update(tri2, num, -1); long long leftLess = query(tri1, num - 1); long long leftMore = query(tri1, maxv) - query(tri1, num); long long rightLess = query(tri2, num - 1); long long rightMore = query(tri2, maxv) - query(tri2, num); ans += leftLess * rightMore; ans += leftMore * rightLess; // 当前元素加入左侧 update(tri1, num, 1); } cout << ans << endl; return 0; }

JAVA

import java.util.*; public class Main { // 树状数组更新 static void update(int[] tree, int index, int delta) { int n = tree.length - 1; while (index <= n) { tree[index] += delta; // 更新当前位置 index += index & -index; // 跳到父区间 } } // 树状数组查询前缀和 static int query(int[] tree, int index) { int res = 0; while (index > 0) { res += tree[index]; index -= index & -index; } return res; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] nums = new int[n]; int maxv = 0; for (int i = 0; i < n; i++) { nums[i] = sc.nextInt(); maxv = Math.max(maxv, nums[i]); } int[] tri1 = new int[maxv + 1]; int[] tri2 = new int[maxv + 1]; // tri2 初始放所有元素 for (int x : nums) { update(tri2, x, 1); } long ans = 0; for (int num : nums) { // 当前元素从右侧移除 update(tri2, num, -1); long leftLess = query(tri1, num - 1); long leftMore = query(tri1, maxv) - query(tri1, num); long rightLess = query(tri2, num - 1); long rightMore = query(tri2, maxv) - query(tri2, num); ans += leftLess * rightMore + leftMore * rightLess; // 当前元素加入左侧 update(tri1, num, 1); } System.out.println(ans); } }

Python

# 树状数组更新defupdate(tree,index,delta):n=len(tree)-1whileindex<=n:tree[index]+=delta index+=index&-index# 树状数组查询前缀和defquery(tree,index):res=0whileindex>0:res+=tree[index]index-=index&-indexreturnres n=int(input())nums=list(map(int,input().split()))maxv=max(nums)tri1=[0]*(maxv+1)tri2=[0]*(maxv+1)# tri2 放所有元素forxinnums:update(tri2,x,1)ans=0fornuminnums:# 从右侧移除update(tri2,num,-1)leftLess=query(tri1,num-1)leftMore=query(tri1,maxv)-query(tri1,num)rightLess=query(tri2,num-1)rightMore=query(tri2,maxv)-query(tri2,num)ans+=leftLess*rightMore+leftMore*rightLess# 加入左侧update(tri1,num,1)print(ans)

JavaScript

constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinputLines=[];rl.on("line",line=>{inputLines.push(line.trim());}).on("close",()=>{constn=parseInt(inputLines[0]);constnums=inputLines[1].split(" ").map(Number);constmaxv=Math.max(...nums);consttri1=newArray(maxv+1).fill(0);consttri2=newArray(maxv+1).fill(0);// 树状数组更新functionupdate(tree,index,delta){letn=tree.length-1;while(index<=n){tree[index]+=delta;index+=index&-index;}}// 树状数组查询前缀和functionquery(tree,index){letres=0;while(index>0){res+=tree[index];index-=index&-index;}returnres;}// 初始tri2 放所有元素for(letxofnums)update(tri2,x,1);letans=0;for(letnumofnums){// 从右侧移除update(tri2,num,-1);letleftLess=query(tri1,num-1);letleftMore=query(tri1,maxv)-query(tri1,num);letrightLess=query(tri2,num-1);letrightMore=query(tri2,maxv)-query(tri2,num);ans+=leftLess*rightMore+leftMore*rightLess;// 加入左侧update(tri1,num,1);}console.log(ans);});

Go

packagemainimport("bufio""fmt""os""strconv""strings")// 树状数组更新funcupdate(tree[]int,index,deltaint){n:=len(tree)-1forindex<=n{tree[index]+=delta index+=index&-index}}// 树状数组查询前缀和funcquery(tree[]int,indexint)int{res:=0forindex>0{res+=tree[index]index-=index&-index}returnres}funcmain(){reader:=bufio.NewReader(os.Stdin)line1,_:=reader.ReadString('\n')n,_:=strconv.Atoi(strings.TrimSpace(line1))line2,_:=reader.ReadString('\n')parts:=strings.Fields(line2)nums:=make([]int,n)maxv:=0fori:=0;i<n;i++{nums[i],_=strconv.Atoi(parts[i])ifnums[i]>maxv{maxv=nums[i]}}tri1:=make([]int,maxv+1)tri2:=make([]int,maxv+1)// 初始tri2 放所有元素for_,x:=rangenums{update(tri2,x,1)}varansint64=0for_,num:=rangenums{// 从右侧移除update(tri2,num,-1)leftLess:=int64(query(tri1,num-1))leftMore:=int64(query(tri1,maxv)-query(tri1,num))rightLess:=int64(query(tri2,num-1))rightMore:=int64(query(tri2,maxv)-query(tri2,num))ans+=leftLess*rightMore+leftMore*rightLess// 加入左侧update(tri1,num,1)}fmt.Println(ans)}