Java 篮球队分组算法：最大能力值球员优先选择

问题描述：

某次篮球比赛前，需要将站成一排的n名球员分为两队(两队人数可以不同)，每名球员的能力值为ai。有两名教练轮流挑选队员，第一个教练先挑选。每位教练每次选人时，都会选择当前剩余的所有人中，能力值最大的那一个。当选择一个人后，会将他左右两侧各m个人一起挑选走(若某一侧可选的人数不够m人，则将这一侧能选的人都选上)。请输出此规则下，分到两队的具体成员情况。

输入描述：

第一行两个正整数，球员人数n，一起挑定的球员左右各m人; 第二行n个正整数，每名球员的能力值ai。

输出描述： 个长度为n的字符串，第i位只包含'A'和'B'，'A'表示第i名球员被挑选到第一个队伍，'B'代表第二个队伍。

解题思路：

根据题目描述，每次教练选择球员时，都会选择当前剩余的所有人中，能力值最大的那一个，并将他左右两侧m个人一起挑选走。我们可以使用一个优先队列来存储球员的能力值，每次选择时，从队列中取出能力值最大的球员，并将他左右两侧m个人一起挑选走。同时，我们使用一个数组来记录每个球员的队伍，初始时都为0，表示未分配队伍。每次挑选球员时，将球员的队伍标记为1或2，表示分到第一个队伍或第二个队伍。

具体实现步骤如下：

读取输入的n和m；
读取n个球员的能力值，并将能力值和球员的编号放入优先队列中；
创建一个长度为n的字符数组team，用于记录球员的队伍；
创建一个长度为n的整型数组chosen，用于记录球员是否被选择过，初始都为0；
创建一个整型变量coach，用于记录当前选择球员的教练编号，初始为1；
循环选择球员，直到优先队列为空： a. 从优先队列中取出能力值最大的球员，并记录其编号为player； b. 将球员的队伍标记为coach，并将其左右两侧m个人的队伍也标记为coach； c. 将player添加到结果字符串result中，并更新chosen数组； d. 切换教练，如果当前教练为1，则切换为2；如果当前教练为2，则切换为1；
输出结果字符串result。

时间复杂度分析：

将球员的能力值放入优先队列中的时间复杂度为O(nlogn)，选择球员的过程中，每个球员最多会被选取两次，因此时间复杂度为O(n)。因此，总的时间复杂度为O(nlogn)。

空间复杂度分析：

除了输入和输出的空间外，需要额外使用一个优先队列、一个字符数组和一个整型数组来存储中间结果，因此空间复杂度为O(n)。

代码实现如下：

import java.util.PriorityQueue;
import java.util.Scanner;

public class BasketballTeamSelection {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 球员人数
        int m = scanner.nextInt(); // 左右两侧选人数量
        int[] abilities = new int[n]; // 球员能力值
        for (int i = 0; i < n; i++) {
            abilities[i] = scanner.nextInt();
        }

        // 使用优先队列存储球员的能力值和编号，并按照能力值降序排序
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < n; i++) {
            queue.offer(new int[]{abilities[i], i});
        }

        // 创建数组记录球员所属队伍，初始值为0，表示未分配队伍
        char[] team = new char[n];
        for (int i = 0; i < n; i++) {
            team[i] = '0';
        }

        // 创建数组记录球员是否被选择过，初始值为0，表示未被选择
        int[] chosen = new int[n];

        // 当前选择球员的教练编号，初始值为1
        int coach = 1;

        // 循环选择球员，直到优先队列为空
        while (!queue.isEmpty()) {
            // 取出能力值最大的球员
            int[] player = queue.poll();
            int playerId = player[1];

            // 将球员的队伍标记为当前教练编号，并将其左右两侧m个人的队伍也标记为当前教练编号
            team[playerId] = (coach == 1) ? 'A' : 'B';
            for (int i = playerId - m; i <= playerId + m && i >= 0 && i < n; i++) {
                if (i != playerId && chosen[i] == 0) {
                    team[i] = (coach == 1) ? 'A' : 'B';
                    chosen[i] = 1;
                }
            }

            // 将球员标记为已选择
            chosen[playerId] = 1;

            // 切换教练
            coach = (coach == 1) ? 2 : 1;
        }

        // 输出结果字符串
        for (int i = 0; i < n; i++) {
            System.out.print(team[i]);
        }
        System.out.println();
    }
}

代码说明：

使用 PriorityQueue 存储球员的能力值和编号，并按照能力值降序排序，以便每次取出能力值最大的球员。
使用 char 数组 team 记录球员所属队伍，'A' 表示第一个队伍，'B' 表示第二个队伍，初始值为 '0' 表示未分配队伍。
使用 int 数组 chosen 记录球员是否被选择过，初始值为 0 表示未被选择，1 表示已选择。
使用 int 变量 coach 记录当前选择球员的教练编号，初始值为 1。
循环选择球员，直到优先队列为空：
- 取出能力值最大的球员，并记录其编号。
- 将球员的队伍标记为当前教练编号，并将其左右两侧 m 个人的队伍也标记为当前教练编号。
- 将球员标记为已选择。
- 切换教练。
输出 team 数组，即每个球员所属的队伍。

注意：

代码中使用了 Java 的 PriorityQueue 类，需要导入 java.util.PriorityQueue 包。
代码中使用了 Java 的 Scanner 类，需要导入 java.util.Scanner 包。
代码中使用了 Java 的 System.out.print 和 System.out.println 方法，用于输出结果字符串。
代码中使用了 Java 的 for 循环和 while 循环，用于遍历数组和选择球员。
代码中使用了 Java 的 if 语句，用于判断球员是否被选择过，以及是否在球员左右两侧 m 个人的范围内。

示例输入：

6 1
10 5 8 2 9 4

示例输出：

ABABB

**解释：**

第一个教练选择能力值为 10 的球员，并将该球员左右各 1 个人一起选择，即选择球员 1、2 和 3，将他们分配到第一个队伍。
第二个教练选择能力值为 9 的球员，并将该球员左右各 1 个人一起选择，即选择球员 4、5 和 6，将他们分配到第二个队伍。
最终输出结果为 `ABABB`，表示第一个队伍的成员为球员 1、2 和 3，第二个队伍的成员为球员 4、5 和 6。

**总结：**

本算法解决了篮球队分组问题，根据球员能力值，教练轮流选择最大能力值球员及其左右两侧 m 个人，输出两队成员分配结果。算法使用优先队列和数组实现，时间复杂度为 O(nlogn)，空间复杂度为 O(n)。