【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 部门组队编程(200分)

本文主要是介绍【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 部门组队编程(200分) - 三语言AC题解(Python/Java/Cpp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

💻 ACM银牌🥈| 多次AK大厂笔试｜编程一对一辅导

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

📎在线评测链接

https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1060

🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁～

🍓OJ题目截图

在这里插入图片描述

文章目录

- 📎在线评测链接
- 🍓OJ题目截图
- 🍊 部门组对编程
- - 问题描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码

🍊 部门组对编程

问题描述

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

$l e v e l [i] < l e v e l [j] < l e v e l [k]$
$l e v e l [i] > l e v e l [j] > l e v e l [k]$

其中， $\le i < j < k < n$ 。

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

输入格式

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

第二行输入 $n$ 个正整数，以空格分隔，表示按员工序号排列的职级 $l e v e l [0]$ 到 $l e v e l [n - 1]$ 。

输出格式

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

样例输入

4
1 2 3 4

样例输出

样例输入

3
5 4 7

样例输出

数据范围

$\le n \le 6000$
$\le level[i] \le 10^5$

题解

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

具体步骤如下：

读入员工总数 $n$ 以及每个员工的职级 $l e v e l$ 。
正序计算每个员工作为中间位置所能组成的小组数量：
- 对于第 $i$ 个员工，统计其左侧职级比他低的人数 $l e f t [i]$ 。
- 对于第 $i$ 个员工，统计其右侧职级比他高的人数 $r i g h t [i]$ 。
- 累加 $\times right[i]$ 到答案中。
将员工职级序列反转，然后重复步骤 2。

参考代码

Python

n = int(input())
level = list(map(int, input().split()))def count_groups(level):n = len(level)res = 0left = [0] * nright = [0] * nfor i in range(n):for j in range(i):if level[j] < level[i]:left[i] += 1for j in range(i + 1, n):if level[j] > level[i]:right[i] += 1for i in range(n):res += left[i] * right[i]return resres = 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;}
}

#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;
}