【华为OD-E卷 - 篮球比赛 100分（python、java、c++、js、c）】
题目
篮球(5V5)比赛中，每个球员拥有一个战斗力，每个队伍的所有球员战斗力之和为该队伍的总体战斗力。
现有10个球员准备分为两队进行训练赛，教练希望2个队伍的战斗力差值能够尽可能的小，以达到最佳训练效果。
给出10个球员的战斗力，如果你是教练，你该如何分队，才能达到最佳训练效果?请说出该分队方案下的最小战斗力差值
输入描述
- 0个篮球队员的战斗力(整数，范围[1,10000]),战斗力之间用空格分隔，如:10987654321
不需要考虑异常输入的场景
输出描述
- 最小的战斗力差值，如:1
用例
用例一：
输入：
10 9 8 7 6 5 4 3 2 1
输出：
1
说明 1 2 5 9 10分为一队，3 4 6 7 8分为一队，两队战斗力之差最小，输出差值1。备注：球员分队方案不唯一，但最小战斗力差值固定是1
python解法
- 解题思路：
- 问题描述：给定一组球员的能力值，将球员分成两队，每队5人，要求两队的能力值之差的绝对值最小。返回最小的能力值差。
思路分析：
组合生成：用 itertools.combinations 生成所有可能的5人队伍。
能力值计算：计算当前组合的总能力值，另一队的能力值等于总能力减去当前组合的能力值。
差值比较：计算两队能力值的差的绝对值，并更新最小差值。
优化：由于组合生成的时间复杂度较高，适合用于小规模输入，10个球员的场景是可接受的
from itertools import combinations
def get_min_diff_power(players):
# 总能力值，所有球员的能力值求和
total_power = sum(players)
# 初始化最小差值为正无穷
min_diff = float('inf')
# 遍历所有可能的5人组合
for team in combinations(players, 5):
# 当前组合的能力值
team_power = sum(team)
# 另一队的能力值
other_team_power = total_power - team_power
# 更新最小差值
min_diff = min(min_diff, abs(team_power - other_team_power))
# 返回最小的能力值差
return min_diff
# 输入球员的能力值，使用空格分隔，转换为整数列表
players = list(map(int, input().split()))
# 输出最小能力值差
print(get_min_diff_power(players))
java解法
- 解题思路
排序：对输入数组进行排序，方便处理和优化递归。
组合生成：通过递归生成所有可能的5人队伍，并计算其能力值的总和。
差值计算：利用队伍的能力值总和计算两队差值的绝对值。
最小值判断：通过 stream 找到最小差值并返回。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] nums = new int[10]; // 输入的10个球员的能力值
for (int i = 0; i < 10; i++) {
nums[i] = sc.nextInt(); // 依次读取能力值
}
// 输出最小的能力值差
System.out.println(findMinDiff(nums));
}
// 寻找最小能力值差
public static int findMinDiff(int[] nums) {
Arrays.sort(nums); // 将数组排序，便于递归处理（可优化剪枝）
ArrayList<Integer> teamSums = new ArrayList<>(); // 存储所有5人队伍的能力值总和
calculateCombinations(nums, 0, 0, 0, teamSums); // 递归生成组合并计算能力值总和
int totalSum = Arrays.stream(nums).sum(); // 计算所有球员的总能力值
// 遍历所有组合能力值，计算两队能力值差，并返回最小值
return teamSums.stream()
.map(subSum -> Math.abs(totalSum - 2 * subSum)) // totalSum - 2 * subSum 是差值公式
.min(Integer::compare) // 找到最小值
.orElse(0); // 若列表为空，返回0
}
// 递归生成所有可能的5人队伍，并计算能力值总和
public static void calculateCombinations(int[] nums, int start, int depth, int sum, ArrayList<Integer> results) {
if (depth == 5) { // 当选择了5人时，记录当前组合的能力值总和
results.add(sum);
return;
}
// 遍历当前起点之后的所有球员
for (int i = start; i < 10; i++) {
// 避免重复组合，例如相邻两个球员能力值相同时跳过
if (i > start && nums[i] == nums[i - 1]) continue;
// 递归选择下一个球员
calculateCombinations(nums, i + 1, depth + 1, sum + nums[i], results);
}
}
}
C++解法
- 解题思路
更新中
C解法
更新中
JS解法
解题分析：
假设数组总和为 totalPower，子集1的和为 partialSum，子集2的和为 totalPower - partialSum。
差值为 Math.abs(totalPower - 2 * partialSum)。
目标是找到一个 partialSum，使得上述差值最小。
解决方法：
遍历所有可能的子集，计算每个子集的和。
用递归的方法生成所有可能的子集和。
对于每种可能的子集和，计算差值并找到最小值。
优化：
使用一个数组保存所有的子集和，避免重复计算。
由于组合的数量较大，可以通过限制子集的大小（如限制子集大小为5）来减少计算量。
const readline = require("readline"); // 引入 readline 模块，用于处理标准输入输出
// 创建一个 readline 接口，用于从命令行读取输入
const rl = readline.createInterface({
input: process.stdin, // 标准输入
output: process.stdout, // 标准输出
});
// 监听每一行输入
rl.on("line", (line) => {
const arr = line.split(" ").map(Number); // 将输入的字符串分割成数组，并转换为数字
console.log(findMinDifference(arr)); // 调用函数计算最小差值，并打印结果
});
/**
* 主函数：找到两个子集和的最小差值
* @param {number[]} arr 输入的整数数组
* @returns {number} 最小差值
*/
function findMinDifference(arr) {
arr.sort((a, b) => a - b); // 对数组进行排序，便于后续处理
const allCombinations = []; // 存储所有子集和
findCombinations(arr, 0, 0, 0, allCombinations); // 调用递归函数生成所有可能的子集和
const totalPower = arr.reduce((acc, val) => acc + val, 0); // 计算数组的总和
// 遍历所有子集和，计算差值并返回最小差值
return allCombinations
.map((partialSum) => Math.abs(totalPower - 2 * partialSum)) // 计算每种子集和的差值
.sort((a, b) => a - b)[0]; // 返回最小差值
}
/**
* 递归函数：生成所有可能的子集和
* @param {number[]} arr 输入数组
* @param {number} start 当前起始索引
* @param {number} depth 当前子集的深度
* @param {number} partialSum 当前子集的和
* @param {number[]} result 保存所有子集和的数组
*/
function findCombinations(arr, start, depth, partialSum, result) {
if (depth === 5) { // 如果当前子集的大小达到5
result.push(partialSum); // 将当前子集的和加入结果数组
return; // 结束当前递归
}
// 遍历数组中的每个元素，从 start 开始
for (let i = start; i < arr.length; i++) {
findCombinations(arr, i + 1, depth + 1, partialSum + arr[i], result);
// 递归：选择当前元素，更新索引、深度和子集和
}
}
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
