华为OD机试真题【篮球比赛】

1、题目描述

【篮球比赛】
一个有N个选手参加比赛，选手编号为1~N（3<=N<=100），有M（3<=M<=10）个评委对选手进行打分。
打分规则为每个评委对选手打分，最高分10分，最低分1分。
请计算得分最多的3位选手的编号。
如果得分相同，则得分高分值最多的选手排名靠前
(10分数量相同，则比较9分的数量，以此类推，用例中不会出现多个选手得分完全相同的情况)。
【输入描述】
10个篮球队员的战斗力(整数,范围[1, 10000])，战斗力之间用空格分隔，如:10987654321
不需要考虑异常输入的场景。
【输出描述】
最小的战斗力差值，如:1
【示例1】
【输入】
10 9 8 7 6 5 4 3 2 1
【输出】
说明: .
1 2 5 9 10分为一队，3 4 6 7 8分为一队，两队战斗之差最小，输出差值1。
备注:球员分队方案不唯一 ，但最小战斗力差值固定是1。

2、解题思路

该题类似于将10个数分成两组，使得两组的数和之差最小。最小战斗力从差值0开始，不满足依次增加，差值为0，即将10个战斗力之和平分给两组，若无法平分则不满足，差值增加。若满足则利用回溯算法统计满足选出5个数且之后恰好为平均值的数。

3、参考代码

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

/**
 * @Author 
 * @Date 2023/6/11 15:15
 */
public class 篮球比赛 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int[] array = Arrays.stream(in.nextLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();

            int totalSum = 0;
            for (int arr : array) {
                totalSum += arr;
            }

            // 从0开始找最小差值战斗力
            for (int i = 0; i <= totalSum; i++) {
                int target = (totalSum - i);
                if (target % 2 == 0) {  // 总和减去差值可以被平分为两组
                    if (dfs(array, 0, target / 2, new boolean[10])) {
                        System.out.println(i);  // 能匹配则输出
                        break;
                    }
                }
            }

        }
    }

    // 回溯 遍历搜索分配球员
    public static boolean dfs(int[] array, int startIndex, int sum, boolean[] used) {
        if (startIndex > 5 || sum < 0) {
            return false;
        }
        if (startIndex == 5 && sum == 0) {
            return true;
        }

        for (int i = 0; i < array.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            if (dfs(array, startIndex + 1, sum - array[i], used)) {
                return true;
            }
            used[i] = false;  // 回溯 不选
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

4、相似题目

（1）代码随想录回溯算法组合题型