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

ops/2024/12/25 14:07:53/

pythonjavacjsc_0">【华为OD-E卷-木板 100分(pythonjava、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_52">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。

python">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_96">java解法

  • 解题思路
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。

javascript">// 最大长度查找函数
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));  // 调用函数输出结果
});

注意:

如果发现代码有用例覆盖不到的情况,欢迎反馈!会在第一时间修正,更新。
解题不易,如对您有帮助,欢迎点赞/收藏


http://www.ppmy.cn/ops/144859.html

相关文章

决策树(理论知识1)

目录 何为决策树决策树的组成决策树的构建 何为决策树 决策树(Decision Tree)是一种分类和回归方法&#xff0c;是基于各种情况发生的所需条件构成决策树&#xff0c;以实现期望最大化的一种图解法。由于这种决策 分支画成图形很像一棵树的枝干&#xff0c;故称决策树。它的运…

《解锁 Python 数据分析的强大力量》

《 解锁 Python 数据分析的强大力量》 一、Python 数据分析的崛起二、Python 数据分析基础&#xff08;一&#xff09;编程基础&#xff08;二&#xff09;数据分析相关库 三、数据分析流程全解析&#xff08;一&#xff09;数据获取&#xff08;二&#xff09;数据存储&#x…

tcp 的重传,流量控制,拥塞控制

tcp 的重传解决了什么问题tcp的几种重传机制分别解决什么问题?方案 1: 超时重传方案2: 快速重传选择性确认(sack)d-sack(重复接收) 滑动窗口:累计应答 流量控制解决什么问题?如何做的?问题1: 那如果第一次发送的数据都大于缓冲区的大小怎么办?问题2: 如果剩余大小为0会发生…

XILINX平台LINUX下高速ADC08060驱动

前置调研 原理图 AXI-FULL时序 由于项目需要实时性高&#xff0c;采用AXI-FULL接口ADC IP作为master端写入DDR中 引用&#xff1a; AXI_02 AXI4总线简介&#xff08;协议、时序&#xff09;_axi4总线时序-CSDN博客 AXI总线的访问 在ARM架构中&#xff0c;访问I/O地址通常通…

nacos-服务发现注册

服务发现注册分为三个角色&#xff1a;服务注册中心、服务提供者、服务消费者 服务注册中心&#xff1a;为服务提供者和消费者提供一个空间&#xff0c;服务提供者将自身服务注册到注册中心&#xff0c;仅对外暴露接口&#xff0c;服务消费者在将自身注册到注册中心的时候也会获…

React 前端框架简介

React 前端框架简介 React 是一个高效、灵活且开源的 JavaScript 库&#xff0c;用于构建用户界面 (UI)。 它专注于 视图层&#xff0c;通常与其他工具结合使用来开发复杂的前端应用。 为什么选择 React&#xff1f; 轻量灵活&#xff1a;仅负责视图层&#xff0c;适配多种框…

C++如何处理对象的状态变化?如何实现工厂模式?

1&#xff09;如何处理对象的状态变化&#xff1f; 在 C中&#xff0c;可以通过以下几种方式处理对象的状态变化&#xff1a; 一、成员函数 成员函数可以修改对象的内部状态。例如&#xff1a; class MyClass { private:int value; public:MyClass(int initialValue) : value(i…

[c++11(二)]Lambda表达式和Function包装器及bind函数

1.前言 Lambda表达式着重解决的是在某种场景下使用仿函数困难的问题&#xff0c;而function着重解决的是函数指针的问题&#xff0c;它能够将其简单化。 本章重点&#xff1a; 本章将着重讲解lambda表达式的规则和使用场景&#xff0c;以及function的使用场景及bind函数的相关使…