当前位置：首页 > article >正文

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

article 2024/12/25 15:48:16

【华为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 2
4 5 3 5 5

输出：

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  # 初始范围，最小值是数组的最小元素，最大值是数组最大值加上m
    best = low  # 保存当前找到的最佳长度

    while low <= high:  # 二分查找
        mid = (low + high) // 2  # 计算中间值
        if can_achieve_length(mid, a, m):  # 如果可以通过m次操作使所有元素至少为mid
            best = 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中的最大值加上操作次数m

    while (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，说明可以尝试更大的mid
            low = mid;  // 更新low值
        } else {  // 否则，减少mid
            high = 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和m
    const a = input[1].split(' ').map(Number);  // 解析数组a
    console.log(maxMinLength(m, a));  // 调用函数输出结果
});