华为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;}
}

4、相似题目

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