【華為OD-E卷-木板 100分（python、java、c++、js、c）】

題目

小明有 n 塊木板，第 i ( 1 ≤ i ≤ n ) 塊木板長度為 ai。

小明買了一塊長度為 m 的木料，這塊木料可以切割成任意塊，拼接到已有的木板上，用來加長木板。

小明想讓最短的模板盡量長。請問小明加長木板后，最短木板的長度可以為多少？

輸入描述

• 輸入的第一行包含兩個正整數， n ( 1 ≤ n ≤ 10^3 ), m ( 1 ≤ m ≤ 10^6 )，n 表示木板數， m 表示木板長度。

輸入的第二行包含 n 個正整數， a1, a2,…an ( 1 ≤ ai ≤ 10^6 )

輸出描述

• 輸出的唯一一行包含一個正整數，表示加長木板后，最短木板的長度最大可以為多少？

用例

用例一：

輸入：

5 3
4 5 3 5 5

輸出：

5

用例二：

輸入：

5 2
4 5 3 5 5

輸出：

4

python解法

• 解題思路：
• 本題的目的是找到一個最大長度，使得我們可以通過給定的操作數量 m 來調整數組 a 中的元素，使得所有元素都至少達到該長度。每次操作可以增加某個元素的值。我們希望通過二分法來高效地找到這個最大長度。

具體步驟：
輸入分析：首先，輸入的是兩個整數 n 和 m，分別表示數組 a 的長度和我們可以進行的操作次數。接著輸入一個整數列表 a，表示數組的初始值。

核心問題：我們需要判斷是否可以通過最多 m 次操作將所有元素增加到某個長度 L（即 L 為數組中的最小值）。為了檢查是否能達到某個長度 L，我們可以計算將每個元素增加到 L 所需的操作次數。如果總操作次數不超過 m，則說明可以實現。

二分查找：為了快速找到最大長度，可以用二分查找：

low 初始化為數組中的最小值，high 初始化為數組中的最大值加上 m，因為最多可以將數組元素增加 m。
在二分查找過程中，每次判斷當前中點 mid 是否能通過 m 次操作實現。如果能，則嘗試增大 mid；如果不能，則減小 mid。
判斷函數：can_achieve_length 用于判斷是否能將所有元素至少調整到某個長度 length，它的核心是計算每個元素需要增加多少才能達到該長度，并判斷是否總操作數不超過 m。

n, m = map(int, input().split())  # 讀取n和m，n是數組的長度，m是可以進行的操作次數
a = list(map(int, input().split()))  # 讀取數組a# 判斷是否能通過m次操作將所有元素調整到至少length的值
def can_achieve_length(length, a, m):needed = sum(max(0, length - x) for x in a)  # 計算所有元素增加到length所需要的操作次數return needed <= m  # 如果操作次數不超過m，則返回True# 利用二分查找找到最大長度
def find_max_length(a, m):low, high = min(a), max(a) + m  # 初始范圍，最小值是數組的最小元素，最大值是數組最大值加上mbest = low  # 保存當前找到的最佳長度while low <= high:  # 二分查找mid = (low + high) // 2  # 計算中間值if can_achieve_length(mid, a, m):  # 如果可以通過m次操作使所有元素至少為midbest = mid  # 更新最佳長度low = mid + 1  # 嘗試尋找更大的值else:high = mid - 1  # 嘗試尋找更小的值return best  # 返回找到的最大長度print(find_max_length(a, m))  # 輸出結果

java解法

• 解題思路

更新中

C++解法

• 解題思路

更新中

C解法

• 解題思路

更新中

JS解法

• 解題思路

• 這道題目要求我們找到一個最大值，使得通過至多 m 次操作，可以將數組 a 中的所有元素調整到至少達到這個值。每次操作可以增加數組元素的值。為了高效地找到這個最大值，我們可以利用 二分查找 的方法。

具體步驟：
輸入分析：輸入的第一個值是 n（數組的長度），第二個是 m（最多可以進行的操作次數）。接著輸入數組 a，其元素表示需要調整的值。

核心問題：對于給定的 m 次操作，能否將數組的所有元素至少增加到某個長度 mid。如果每個元素都小于 mid，就需要增加相應的差值。目標是找出最大的 mid，使得通過至多 m 次操作就能將數組所有元素調整到至少 mid。

二分查找：我們可以通過二分查找來找到這個最大長度 mid，從 low = min(a) 到 high = max(a) + m。每次計算 mid，并判斷是否能通過 m 次操作達到這個長度。如果能，則說明可以嘗試更大的 mid，否則減小 mid。

判斷函數：在每一次的二分查找中，我們需要計算將所有元素調整到 mid 所需的總操作次數，判斷是否不超過 m。

// 最大長度查找函數
function maxMinLength(m, a) {let low = Math.min(...a);  // 初始時，low為數組a中的最小值let high = Math.max(...a) + m;  // high為數組a中的最大值加上操作次數mwhile (low < high) {  // 二分查找const mid = Math.floor((low + high + 1) / 2);  // 計算中點值，向上取整const needed = a.reduce((sum, length) => {  // 計算將所有元素調整到mid所需的操作次數return sum + Math.max(0, mid - length);  // 對于小于mid的元素，計算差值}, 0);if (needed <= m) {  // 如果操作次數不超過m，說明可以嘗試更大的midlow = mid;  // 更新low值} else {  // 否則，減少midhigh = mid - 1;}}return low;  // 最終返回的low即為最大能達到的長度
}// 讀取輸入的部分
const readline = require('readline');
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let input = [];rl.on('line', (line) => {input.push(line);  // 逐行讀取輸入
}).on('close', () => {const [n, m] = input[0].split(' ').map(Number);  // 解析n和mconst a = input[1].split(' ').map(Number);  // 解析數組aconsole.log(maxMinLength(m, a));  // 調用函數輸出結果
});

注意：

如果發現代碼有用例覆蓋不到的情況，歡迎反饋！會在第一時間修正，更新。
解題不易，如對您有幫助，歡迎點贊/收藏