【LeetCode】大厂面试算法真题回忆(122) —— 篮球比赛

题目描述

篮球（5v5）比赛中，每个球员有一个战斗力，每个队伍的总战斗力为队内所有球员战斗力之和。
现有 10 个球员，要求分为两队，且每队 正好 5 人。教练希望两队战斗力差值最小，请输出该最小值。

---

输入描述

输入为 10 个整数（1 ≤ 战斗力 ≤ 10000），表示球员战斗力，空格分隔。

---

输出描述

输出一个整数，表示最小的战斗力差值。

---

示例

示例一

输入：

10 9 8 7 6 5 4 3 2 1

输出：

1

解释：
分组方案之一：

• 队1: 10, 9, 5, 2, 1 = 27
• 队2: 8, 7, 6, 4, 3 = 28
  差值 = 1。

---

解题思路

方法一：贪心法（近似解）

• 按战斗力排序，大的先分给当前总和较小的队伍。
• 快，但不一定是严格最优解（容易在特殊数据下出错）。