返回目录

题目描述

某部门计划通过结队编程来进行项目开发，

已知该部门有 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中 [1,2,3,4] ，每个数组元素：

• 左边比自己大的元素的个数，设为：leftBiggerCount
• 左边比自己小的元素的个数，设为：leftSmallerCount
• 右边比自己大的元素的个数，设为：rightBiggerCount
• 右边比自己小的元素是的个数，设为：rightSmallerCount

当我们求解出每个数组元素的上述信息后，累加每个数组元素的如下计算结果：

leftBiggerCount * rightSmallerCount + leftSmallerCount * rightBiggerCount

暴力解法

定义两层循环，外层确定结队中间值，内层两个平级循环，分别扫描中间值左边，和中间值右边。

Python算法源码

# 定义一个函数来计算结果
def get_result(n, levels):
    ans = 0  # 初始化答案变量

    # 遍历每个元素，除了第一个和最后一个
    for i in range(1, n - 1):
        mid = levels[i]  # 当前元素作为中间值

        # 初始化左侧小于和大于中间值的计数器
        left_smaller_count = 0
        left_bigger_count = 0

        # 遍历中间值左侧的元素
        for j in range(i):
            if levels[j] > mid:
                left_bigger_count += 1  # 如果当前元素大于中间值，增加左侧大于计数
            else:
                left_smaller_count += 1  # 否则，增加左侧小于计数

        # 初始化右侧小于和大于中间值的计数器
        right_smaller_count = 0
        right_bigger_count = 0

        # 遍历中间值右侧的元素
        for k in range(i + 1, n):
            if levels[k] > mid:
                right_bigger_count += 1  # 如果当前元素大于中间值，增加右侧大于计数
            else:
                right_smaller_count += 1  # 否则，增加右侧小于计数

        # 累加到总答案中：左侧小于计数 * 右侧大于计数 + 左侧大于计数 * 右侧小于计数
        ans += left_smaller_count * right_bigger_count + left_bigger_count * right_smaller_count

    return ans  # 返回最终的答案

# 主程序开始
# 获取输入的数量和各个元素值
n = int(input())
levels = list(map(int, input().split()))

# 调用函数计算结果并打印
print(get_result(n, levels))

C算法源码

#include <stdio.h>

// 定义函数用于计算结果
int getResult(int levels[], int n) {
    int ans = 0; // 初始化答案变量

    // 遍历数组中除了第一个和最后一个元素之外的元素
    for (int i = 1; i < n - 1; i++) {
        int mid = levels[i]; // 当前元素作为中间值

        int leftSmallerCount = 0; // 初始化左侧小于中间值的计数器
        int leftBiggerCount = 0; // 初始化左侧大于中间值的计数器

        // 统计中间值左侧的小于和大于中间值的元素数量
        for (int j = 0; j < i; j++) {
            if (levels[j] > mid) {
                leftBiggerCount += 1; // 如果当前元素大于中间值，增加左侧大于计数
            } else {
                leftSmallerCount += 1; // 否则，增加左侧小于计数
            }
        }

        int rightSmallerCount = 0; // 初始化右侧小于中间值的计数器
        int rightBiggerCount = 0; // 初始化右侧大于中间值的计数器

        // 统计中间值右侧的小于和大于中间值的元素数量
        for (int k = i + 1; k < n; k++) {
            if (levels[k] > mid) {
                rightBiggerCount += 1; // 如果当前元素大于中间值，增加右侧大于计数
            } else {
                rightSmallerCount += 1; // 否则，增加右侧小于计数
            }
        }

        // 累加到总答案中：左侧小于计数 * 右侧大于计数 + 左侧大于计数 * 右侧小于计数
        ans += leftSmallerCount * rightBiggerCount + leftBiggerCount * rightSmallerCount;
    }

    return ans; // 返回最终的答案
}

int main() {
    int n;
    scanf("%d", &n); // 获取输入的数组大小

    int levels[n]; // 声明一个数组来存储输入的元素

    // 循环读取输入的元素
    for (int i = 0; i < n; i++) {
        scanf("%d", &levels[i]);
    }

    // 调用算法函数计算结果并输出
    printf("%d\n", getResult(levels, n));

    return 0;
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

// 用于统计满足条件的三元组数量的类
class TripletCounter {
    // 统计满足条件的三元组数量
    public static int countTriplets(int[] levels) {
        int res = 0; // 初始化结果变量

        boolean flag = false; // 标志变量，用于指示后续排序方式
        int n = levels.length; // 获取数组长度
        int i = 0;

        // 遍历数组中的元素，i为三元组的第一个元素的索引
        while (i < n - 2) {
            int x = levels[i]; // 第一个元素
            int j = i + 1;

            // 遍历数组中的元素，j为三元组的第二个元素的索引
            while (j < n - 1) {
                int y = levels[j]; // 第二个元素

                // 根据前后元素的大小关系确定后续排序方式
                if (x < y) {
                    // 如果前面的元素小于后面的元素，则后续排序方式为升序
                    flag = false;
                } else {
                    // 如果前面的元素大于后面的元素，则后续排序方式为降序
                    flag = true;
                }
                int k = j + 1;

                // 遍历数组中的元素，k为三元组的第三个元素的索引
                while (k < n) {
                    int z = levels[k]; // 第三个元素

                    // 根据排序方式判断是否满足条件，累加符合条件的三元组数量
                    if (flag) {
                        // 如果需要降序排序，则第二个元素应大于第三个元素
                        res += y > z ? 1 : 0;
                    } else {
                        // 如果需要升序排序，则第二个元素应小于第三个元素
                        res += y < z ? 1 : 0;
                    }
                    k++; // 移动到下一个元素
                }
                j++; // 移动到下一个元素
            }
            i++; // 移动到下一个元素
        }
        return res; // 返回满足条件的三元组数量
    }
}

// 主类
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 获取数组大小
        sc.nextLine(); // 换行

        // 将输入的字符串转换为整数数组
        int[] levels = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        // 调用函数计算结果
        int res = TripletCounter.countTriplets(levels);

        // 输出结果
        System.out.println(res);
    }
}