结队编程 - 华为OD统一考试（D卷）

OD统一考试（D卷）

分值： 200分

题解： Java / Python / C++

题目描述

某部门计划通过结队编程来进行项目开发，已知该部门有 N 名员工，每个员工有独一无二的职级，每三个员工形成一个小组进行结队编程，结队分组规则如下：

从部门中选出序号分别为 i、j、k 的3名员工，他们的职级分别为 level[i]，level[j]，level[k]，结队小组满足 level[i] < level[j] < level[k] 或者 level[i] > level[j] > level[k]，其中 0 ≤ i < j < k < n。

请你按上述条件计算可能组合的小组数量。同一员工可以参加多个小组。

输入描述

第一行输入：员工总数 n

第二行输入：按序号依次排列的员工的职级 level，中间用空格隔开

备注：

1 <= n <= 6000

1 <= level[i] <= 10^5

输出描述

可能结队的小组数量

示例1

输入：
4
1 2 3 4

输出：
4

说明：
可能结队成的组合(1,2,3)、(1,2,4)、(1,3,4)、(2,3,4)

示例2

输入：
3
5 4 7

输出：
0

说明：
根据结队条件，我们无法为该部门组建小组

题解

此解法是在暴力的基础上进行了优化。

我们考虑预处理每个员工左侧和右侧的符合条件的员工数量。具体来说，对于每个员工，我们需要知道其左侧和右侧大于和小于其职级的员工数量。然后，通过这些预处理的数量来快速计算满足条件的组合数量。

虽然对于最大值6000可能会超时，但是可以获得大多数分数（C++可以AC95%比暴力解法得分更高）。

具体步骤

1. 预处理：使用两次遍历分别计算每个员工左侧和右侧大于和小于其职级的员工数量。
2. 计算组合数量：根据预处理的结果，快速计算满足条件的组合数量。

时间复杂度：使用两次遍历分别计算每个员工左侧和右侧大于和小于其职级的员工数量，因此时间复杂度为 O(n^2)。

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] levels = new int[n];
        for (int i = 0; i < n; i++) {
            levels[i] = scanner.nextInt();
        }

        int[] leftGt = new int[n];
        int[] leftLt = new int[n];
        int[] rightGt = new int[n];
        int[] rightLt = new int[n];

        // 计算左右侧大于和小于当前员工职级的员工数量
        for (int l = 0; l < n; l++) {
            for (int r = l + 1; r < n; r++) {
                if (levels[l] < levels[r]) {
                    leftLt[r]++;
                    rightGt[l]++;
                } else {
                    leftGt[r]++;
                    rightLt[l]++;
                }
            }
        }

        // 计算满足条件的组合数量
        long ans = 0;
        for (int i = 1; i < n - 1; i++) {
            ans += leftLt[i] * rightGt[i] + leftGt[i] * rightLt[i];
        }

        System.out.println(ans);
    }
}

Python

def count_teams(n, levels):
    left_gt = [0] * n
    left_lt = [0] * n
    right_gt = [0] * n
    right_lt = [0] * n

    # 计算左右两侧大于和小于当前员工职级的员工数量
    for l in range(n):
        for r in range(l + 1, n):
            if levels[l] < levels[r]:
                left_lt[r] += 1
                right_gt[l] += 1
            else:
                left_gt[r] += 1
                right_lt[l] += 1

    # 计算满足条件的组合数量
    ans = 0
    for i in range(1, n - 1):
        ans += left_lt[i] * right_gt[i] + left_gt[i] * right_lt[i]

    return ans

# 输入处理
n = int(input())
levels = list(map(int, input().split()))

# 计算结果
result = count_teams(n, levels)
print(result)

C++

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

int main() {
    int n;
    cin >> n;

    vector<int> level(n);
    for(int i = 0; i<n;i++) cin >> level[i];
	
    // left_gt[i] 左侧大于 level[i] 的员工个数
    // left_lt[i] 左侧小于 level[i] 的员工个数
    vector<int> left_gt(n, 0), left_lt(n, 0);
    
	// right_gt[i] 右侧大于 level[i] 的员工个数
    // right_lt[i] 右侧小于 level[i] 的员工个数
    vector<int> right_gt(n, 0), right_lt(n, 0);

    for(int l = 0; l < n; l++){
        for(int r = l + 1; r < n; r++){
            if(level[l] < level[r]){
                left_lt[r]++;
                right_gt[l]++;
            }else{
                left_gt[r]++;
                right_lt[l]++;
            }
        }
    }

    long long rs = 0;
    for(int i = 1; i < n - 1; i++){
        rs += left_lt[i] * right_gt[i] + left_gt[i] * right_lt[i];
    }

    cout << rs << endl;
    
	return 0;
}
// 95 %