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、参考代码
java">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;
}
}