最新华为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[n];
        for (int i = 0; i < n; i++) {
            level[i] = sc.nextInt();
        }
        
        long res = countGroups(level);
        res += countGroups(reverse(level));
        System.out.println(res);
    }
    
    private static long countGroups(int[] level) {
        int n = level.length;
        long res = 0;
        int[] left = new int[n];
        int[] right = new int[n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (level[j] < level[i]) {
                    left[i]++;
                }
            }
            for (int j = i + 1; j < n; j++) {
                if (level[j] > level[i]) {
                    right[i]++;
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            res += (long) left[i] * right[i];
        }
        
        return res;
    }
    
    private static int[] reverse(int[] level) {
        int n = level.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = level[n - i - 1];
        }
        return res;
    }
}

• Cpp

#include <bits/stdc++.h>
using namespace std;

long long countGroups(vector<int>& level) {
    int n = level.size();
    long long res = 0;
    vector<int> left(n, 0), right(n, 0);
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (level[j] < level[i]) {
                left[i]++;
            }
        }
        for (int j = i + 1; j < n; j++) {
            if (level[j] > level[i]) {
                right[i]++;
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        res += (long long) left[i] * right[i];
    }
    
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> level(n);
    for (int i = 0; i < n; i++) {
        cin >> level[i];
    }
    
    long long res = countGroups(level);
    reverse(level.begin(), level.end());
    res += countGroups(level);
    cout << res << endl;
    
    return 0;
}