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

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

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

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

📎在线评测链接

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

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

🍓OJ题目截图

🍊 部门组对编程

问题描述

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

1. $level[i]<level[j]<level[k]$
2. $level[i]>level[j]>level[k]$

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

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

输入格式

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

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

输出格式

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

样例输入

4
1 2 3 4

样例输出

4

样例输入

3
5 4 7

样例输出

0

数据范围

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

题解

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

具体步骤如下：

1. 读入员工总数 $n$ 以及每个员工的职级 $level$。
2. 正序计算每个员工作为中间位置所能组成的小组数量：
   • 对于第 $i$ 个员工，统计其左侧职级比他低的人数 $left[i]$。
   • 对于第 $i$ 个员工，统计其右侧职级比他高的人数 $right[i]$。
   • 累加 $left[i]\times right[i]$ 到答案中。
3. 将员工职级序列反转，然后重复步骤 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;}
}

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