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