2025 A卷 100分 题型
本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；
并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；
本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》
华为OD机试真题《求最多可以派出多少支队伍》：
文章快捷目录
题目描述及说明
Java
python
JavaScript
C
GO
题目名称：求最多可以派出多少支队伍
- 知识点：贪心算法、双指针、排序
- 时间限制：1秒
- 空间限制：256MB
- 限定语言：不限
题目描述
用数组代表每个人的能力，一个比赛活动要求参赛团队的最低能力值为N。每个团队可以由1人或2人组成，且1个人只能参加1个团队。请计算出最多可以派出多少支符合要求的团队？
输入描述：
- 第一行为总人数，范围[1,500000]。
- 第二行为每个人的能力值数组，元素取值范围[1,500000]，数组大小与总人数一致。
- 第三行为团队要求的最低能力值N，范围[1,500000]。
输出描述：
- 最多可以派出的团队数量。
示例：
输入：
5
3 1 5 7 9
8
输出：
3
说明：
- 3和5组成一队（3+5≥8），1和7组成一队（1+7≥8），9单独一队（9≥8），共3队。
Java
问题分析
我们需要从一组人中选出尽可能多的团队，每个团队可以由1人或2人组成，且能力值之和需达到最低要求N。目标是找到最大的团队数量。
解题思路
- 排序数组：将能力值从小到大排序，便于双指针操作。
- 贪心策略：使用双指针，优先让能力大的人单独成队，若不能则尝试与能力小的人组队。
- 双指针操作：
- 右指针从最大能力开始，若单独满足要求则成队。
- 否则尝试与左指针的人组队，若满足则成队，否则左移找更小能力的人。
代码实现
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int total = scanner.nextInt();
int[] abilities = new int[total];
for (int i = 0; i < total; i++) {
abilities[i] = scanner.nextInt();
}
int N = scanner.nextInt();
Arrays.sort(abilities); // 将能力值排序，便于双指针操作
int left = 0; // 左指针，指向当前最小未处理的能力值
int right = total - 1; // 右指针，指向当前最大未处理的能力值
int count = 0; // 统计符合要求的团队数量
while (left <= right) {
// 当还有人未处理时循环
if (abilities[right] >= N) {
// 右指针的人能力值达标，单独成队
count++;
right--; // 处理下一个更大的能力值（指针左移）
} else {
// 右指针的人无法单独成队，尝试与左指针的人组队
if (left < right && abilities[left] + abilities[right] >= N) {
// 左右指针不同且组合达标
count++;
left++; // 左指针右移，处理下一个更小的能力值
right--; // 右指针左移，处理下一个更大的能力值
} else {
// 无法组队，左指针右移（当前右指针的人无法配对，只能放弃）
left++;
}
}
}
System.out.println(count);
}
}
代码详解
- 输入处理：读取总人数、能力数组和最低要求N。
- 排序：将数组排序，便于双指针从两端向中间处理。
- 双指针初始化：
left指向最小元素，right指向最大元素。 - 循环处理：
- 右指针单独成队：若当前右指针的人能力≥N，直接成队。
- 尝试组队：若左右指针非同一人且能力之和≥N，组队。
- 无法处理：左指针右移，放弃当前右指针的人。
- 输出结果：统计所有可能的队伍数量。
示例测试
示例输入1：
5 3 1 5 7 9 8输出：3
说明：3和5组队，1和7组队，9单独成队。示例输入2：
2 4 5 8输出：1
说明：4和5组队。示例输入3：
3 3 3 3 5输出：1
说明：其中两人组队（3+3≥5），剩下一人无法成队。
综合分析
- 时间复杂度：O(n log n)，排序耗时O(n log n)，双指针遍历O(n)。
- 空间复杂度：O(1)，仅使用常量额外空间。
- 正确性：
- 贪心策略确保每次尽可能组成最多的队伍。
- 排序和双指针处理所有可能的组合。
- 适用性：
- 处理大规模数据高效（如50万人）。
- 逻辑清晰，避免复杂递归或动态规划。
- 为何最优：
- 贪心策略优先处理能力大的人，最大化利用高能力值。
- 双指针保证线性时间复杂度，避免重复计算。
python
问题分析
我们需要从一组人中选出尽可能多的团队，每个团队可以由1人或2人组成，且能力值之和需达到最低要求N。目标是找到最大的团队数量。
解题思路
- 排序数组：将能力值从小到大排序，便于双指针操作。
- 贪心策略：使用双指针，优先让能力大的人单独成队，若不能则尝试与能力小的人组队。
- 双指针操作：
- 右指针从最大能力开始，若单独满足要求则成队。
- 否则尝试与左指针的人组队，若满足则成队，否则左移找更小能力的人。
代码实现
def max_teams():
import sys
# 读取输入数据
total = int(sys.stdin.readline()) # 总人数
abilities = list(map(int, sys.stdin.readline().split())) # 能力数组
N = int(sys.stdin.readline()) # 团队最低能力要求
# 将能力数组从小到大排序（排序后：左指针指向最小，右指针指向最大）
abilities.sort()
left = 0 # 左指针初始指向最小值
right = total - 1 # 右指针初始指向最大值
count = 0 # 统计符合要求的团队数量
# 双指针贪心算法
while left <= right:
# 如果当前右指针的人能力值 >= N，单独成队
if abilities[right] >= N:
count += 1
right -= 1 # 处理下一个更大的能力值（右指针左移）
else:
# 尝试与左指针的人组队
if left < right and (abilities[left] + abilities[right] >= N):
count += 1
left += 1 # 左指针右移（处理更小的能力值）
right -= 1 # 右指针左移（处理更大的能力值）
else:
# 无法组队，丢弃当前左指针的人（因为它无法与任何更大的值组队）
left += 1
print(count)
# 示例测试
if __name__ ==