华为OD机试真题 JavaScript 实现【不爱施肥的小布】【2023Q1 100分】

在这里插入图片描述

一、题目描述

某农村主管理了一大片果园，fields[i]表示不同国林的面积，单位m²，现在要为所有的果林施肥且必须在n天之内完成，否则影响收成。小布是国林的工作人员，他每次选择一片果林进行施肥，且一片国林施肥完后当天不再进行施肥作业。

假设施肥机的能效为K，单位：m²/day，请问至少租赁能效K为多少的施肥机才能确保不影响收成？如果无法完成施肥任务，则返回-1。

二、输入描述

第一行输入为m和n，m表示fields中的元素个数，n表示施肥任务必须在n天内（含n天）完成；

第二行输入为fields，fields[i]表示果林i的面积，单位：m²。

三、输出描述

对于每组数据，输出最小施肥机的能效k，无多余空格。

补充说明：

1 <= fields.length <= 10⁴
1 <= n < 10⁹
1<= fields[i] <= 10⁹

四、解题思路

首先读取输入的果园数量 m 和需要完成施肥任务的天数 days；
使用循环读取果园面积，将其存储在整数数组 fields 中；
找到果园面积的最大值，用变量 maxFields 记录；
根据给定的条件进行判断：
- 如果需要完成施肥任务的天数小于果园数量，即 days < m，则无法在规定天数内完成施肥任务，输出 -1；
- 如果需要完成施肥任务的天数等于果园数量，即 days == m，则直接输出最大果园面积 maxFields；
- 否则，调用 getMin() 方法计算最小施肥机的能效 k，并输出结果；
在 getMin() 方法中，使用二分查找来确定最小施肥机的能效 k；
- 初始化二分查找的起始值 start 为 1，终止值 end 为 maxFields；
- 进入循环，直到 start + 1 < end，每次迭代都更新 mid 为 start 和 end 的中间值；
- 在每次迭代中，计算使用当前的 mid 值时所需的总天数 sumDays；
- 遍历果园面积数组 fields，对于每个果园面积，根据能效 mid 计算所需的天数，并累加到 sumDays 中；
- 如果 sumDays 大于给定的天数 days，说明当前的 mid 值太小，需要增大能效，将 start 更新为 mid；
- 否则，将 end 更新为 mid；
返回 start + 1，即为最小施肥机的能效 k；

五、JavaScript算法源码

/*** @param m 果园数量* @param days 需要完成施肥任务的天数* @param input 使用循环读取果园面积*/
function calculate(m, days, input) {const fields = input.split(" ");let maxFields = fields[0];for (let i = 0; i < m; i++) {maxFields = Math.max(maxFields, fields[i]);}// 如果需要完成施肥任务的天数小于果园数量if (days < m) {// 无法在规定天数内完成施肥任务，输出 -1return -1;// 如果需要完成施肥任务的天数等于果园数量} else if (days === m) {// 直接输出最大果园面积 maxFieldsreturn maxFields;} else {// 计算最小施肥机的能效 kreturn getMin(maxFields, fields, days);}
}// 计算最小施肥机的能效
// 使用二分查找来确定最小施肥机的能效
function getMin(max, fields, days) {// 初始化二分查找的起始值let start = 1;// 终止值 end 为 maxlet end = max;// 每次迭代都更新 mid 为 start 和 end 的中间值while (start + 1 < end) {const mid = Math.floor((start + end) / 2);let sumDays = 0;// 对于每个果园面积，根据能效 mid 计算所需的天数，并累加到 sumDays 中for (let i = 0; i < fields.length; i++) {if (fields[i] % mid === 0) {sumDays += fields[i] / mid;} else {sumDays += Math.floor(fields[i] / mid) + 1;}}// 如果 sumDays 大于给定的天数 days，说明当前的 mid 值太小，// 需要增大能效，将 start 更新为 midif (sumDays > days) {start = mid;} else {end = mid;}}return start + 1;
}