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

✨ 本系列打算持续跟新华为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 = 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;
}