最新华为OD机试真题-部门组队编程(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 部门组队编程(200分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🍊 部门组对编程

问题描述

LYA所在的部门计划通过结对编程的方式进行项目开发。已知部门中有 名员工，每个员工都有一个独特的职级。结对编程要求从部门中选出三名员工组成一个小组，设这三名员工的序号分别为 、、，他们的职级分别为 、、，则小组需要满足以下条件之一：

其中，。

请你计算在满足上述条件的情况下，可以组建的小组数量。注意，同一员工可以参与多个小组。

输入格式

第一行输入一个正整数 ，表示员工总数。

第二行输入 个正整数，以空格分隔，表示按员工序号排列的职级 到 。

输出格式

输出一个整数，表示可以组建的小组数量。

样例输入

4
1 2 3 4

样例输出

4

样例输入

3
5 4 7

样例输出

0

数据范围

题解

可以枚举每个员工作为小组的中间位置，然后统计其左侧职级比他低的人数乘以右侧职级比他高的人数，这样就能得到以该员工为中间人所能组成的小组数量。需要注意的是，为了避免重复统计，我们需要将所有员工按照职级从低到高或从高到低排序，然后再进行统计。

具体步骤如下：

1. 读入员工总数 以及每个员工的职级 。
2. 正序计算每个员工作为中间位置所能组成的小组数量：
   • 对于第 个员工，统计其左侧职级比他低的人数 。
   • 对于第 个员工，统计其右侧职级比他高的人数 。
   • 累加 到答案中。
3. 将员工职级序列反转，然后重复步骤 2。

参考代码

• Python

n = int(input())
level = list(map(int, input().split()))

def count_groups(level):
    n = len(level)
    res = 0
    left = [0] * n
    right = [0] * n
    
    for i in range(n):
        for j in range(i):
            if level[j] < level[i]:
                left[i] += 1
        for j in range(i + 1, n):
            if level[j] > level[i]:
                right[i] += 1
    
    for i in range(n):
        res += left[i] * right[i]
    
    return res

res = count_groups(level)
res += count_groups(level[::-1])
print(res)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] level = new int[