2025 A卷 200分 题型

本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！

本文收录于专栏：《2025华为OD真题目录+全流程解析/备考攻略/经验分享》

华为OD机试真题《开放日活动／取出尽量少的球》：

---

---

题目名称：开放日活动／取出尽量少的球

---

• 知识点：二分查找、逻辑处理
• 时间限制：1秒
• 空间限制：256MB
• 限定语言：不限

---

题目描述

某部门开展开放日活动，其中一个游戏是从桶里取球。游戏规则如下：

• 有 N 个容量相同的小桶等距排开，每个小桶默认装有不同数量的小球，记录在数组 bucketBallNums 中。
• 游戏开始时，所有桶的小球总数不能超过 SUM。若超过，需对所有小桶设置统一的容量最大值 maxCapacity，并将超过此值的球取出，直到每个桶的球数不超过 maxCapacity。

限制规则：

1. 总和未超限：若所有桶的总球数 ≤ SUM，返回空数组 []。
2. 总和超限：若总球数 > SUM，需计算 maxCapacity，并返回每个桶取出的小球数量数组。要求 maxCapacity 尽可能大，且取出球数最少。

输入描述：

• 第一行为两个正整数：SUM 和 bucketBallNums 数组长度 N。
• 第二行为 N 个正整数，表示 bucketBallNums 的每个元素。

输出描述：

• 返回一个数组，表示每个桶取出的小球数量。若无需操作，返回 []。

示例：
输入：

14 7  
2 3 2 5 5 1 4  

输出：

[0, 1, 0, 3, 3, 0, 2]  

说明：

• 总球数为 2+3+2+5+5+1+4=22 > 14。
• 设置 maxCapacity=2，各桶保留球数为 [2,2,2,2,2,1,2]，取出球数为 [0,1,0,3,3,0,2]，总和为 9（22-13=9≤14）。

补充说明：

• 1 ≤ N ≤ 1e5，1 ≤ SUM ≤ 1e9，1 ≤ bucketBallNums[i] ≤ 1e9。
• 必须通过二分法高效求解 maxCapacity。

---

Java

问题分析

我们需要在给定多个小桶的情况下，设置一个统一的最大容量 maxCapacity，使得调整后的总球数不超过 SUM。目标是找到最大的 maxCapacity 并计算每个桶需要取出的小球数量。

---

解题思路

1. 初始判断：计算所有桶的总球数，若不超过 SUM，直接返回空数组。
2. 二分查找确定最大容量：
   • 使用二分法在 0 到最大桶球数之间寻找满足总球数条件的最大 maxCapacity。
3. 计算取出球数：根据找到的 maxCapacity，计算每个桶需要取出的小球数量。

---

代码实现

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int SUM = sc.nextInt();int N = sc.nextInt();int[] buckets = new int[N];long total = 0;int maxBall = 0;// 读取桶的初始球数并计算总和及最大值for (int i = 0; i < N; i++) {buckets[i] = sc.nextInt();total += buckets[i];maxBall = Math.max(maxBall, buckets[i]);}// 初始总和未超限，直接返回空数组if (total <= SUM) {System.out.println("[]");return;}// 二分查找确定最大允许的 maxCapacityint left = 0, right = maxBall;int maxCapacity = 0;while (left <= right) {int mid = left + (right - left) / 2;long currentSum = 0;for (int num : buckets) {currentSum += Math.min(num, mid);}if (currentSum <= SUM) {maxCapacity = mid;   // 当前 mid 可能为可行解，尝试更大的值left = mid + 1;} else {right = mid - 1;     // 当前 mid 导致总和过大，减小上限}}// 计算各桶需要取出的球数int[] result = new int[N];for (int i = 0; i < N; i++) {result[i] = buckets[i] - Math.min(buckets[i], maxCapacity);}// 格式化输出System.out.println(Arrays.toString(result).replace(" ", ""));}
}

---

代码详细解析

1. 输入处理：

   • 使用 Scanner 读取输入的 SUM 和桶的数量 N。
   • 读取每个桶的球数存入数组 buckets，并计算总球数 total 及最大值 maxBall。

2. 初始判断：

   • 若初始总球数 total 不超过 SUM，直接输出空数组 []。

3. 二分查找：

   • 范围设定：左边界 left 为 0，右边界 right 为最大桶球数 maxBall。
   • 循环条件：当 left <= right 时，计算中间值 mid，并计算当前 mid 对应的总球数 currentSum。
   • 调整策略：若 currentSum <= SUM，说明可以尝试更大的 mid，调整 left；否则调整 right。

4. 计算取出球数：

   • 遍历每个桶，计算其需要取出的小球数量，即原始球数减去调整后的球数。

5. 输出处理：

   • 使用 Arrays.toString 将结果数组转换为字符串，并去除空格以符合题目要求。

---

示例测试

示例1输入：

14 7  
2 3 2 5 5 1 4  

输出：

[0,1,0,3,3,0,2]

解析：最大容量为 2，取出球数总和为 9，调整后总球数为 13 ≤ 14。

示例2输入：

0 1  
1  

输出：

[1]

解析：总球数 1 > 0，设置最大容量为 0，取出所有球。

示例3输入：

10 3  
5 5 5  

输出：

[0,0,0]

解析：初始总球数 15 > 10，最大容量设为 3，调整后总球数为 9 ≤ 10。

---

综合分析

1. 时间复杂度：O(N log M)，其中 N 是桶的数量，M 是最大桶球数。二分查找的复杂度为 O(log M)，每次查找需遍历数组。
2. 空间复杂度：O(N)，存储桶的球数数组和结果数组。
3. 优势：
   • 高效查找：二分法快速定位最大容量。
   • 避免冗余计算：每次遍历仅计算当前中间值的总球数。
4. 适用场景：适用于大规模数据（桶数 ≤ 1e5）的场景，满足时间限制要求。

---

python

问题分析

我们需要在给定多个桶的情况下，设置一个统一的最大容量 maxCapacity，使得调整后的总球数不超过 SUM。目标是找到最大的 maxCapacity 并计算每个桶需要取出的小球数量。

---

解题思路

1. 初始判断：计算所有桶的总球数，若不超过 SUM，直接返回空数组。
2. 二分查找确定最大容量：
   • 使用二分法在 0 到最大桶球数之间寻找满足总球数条件的最大 maxCapacity。
3. 计算取出球数：根据找到的 maxCapacity，计算每个桶需要取出的小球数量。

---

代码实现

def main():import sysinput