2024年美团秋招第四轮笔试编程题第2题

小美请工人在一条无限长的公路上种树，每个工人只能在自己位置和自己右边位置依次种树，每个位置只能种1棵树，每个工人种树数量都相等为k，工人总数为n，小美希望种下的树的总数至少是m，本题第一行将输入两个数字（以空格隔开），分别是工人数量n、小美希望种下树的总数m，第二行将输入表示工人位置的数字序列（以空格隔开），求出每个工人种树数量k的最小值。

示例如下

输入：

3 6

1 2 4

输出：3 。即工人1在位置1，在1、2、3号位种树；工人2在位置2，在2、3、4号位种树；工人3在位置4，在4、5、6号位种树。不存在比3更小的种树数量了。

我当时以为自己做出来了，测试用例也通过了，但提交之后却是错的，求问各位有思路分享吗？

更新：复现了当时的代码，发现是排序后取值边界的细节搞错了，明明思路想对了然而白白扣掉40分

// 美团2024秋招第四轮笔试编程题2 -- 种树
// https://www.nowcoder.com/discuss/659520408298782720
// 工人总数，要求种下的树的总数，工人位置数组  :  返回值是 每个工人最小种树数量
function plantTree(workerNum, treeNum, positions) {
  let distance = []
  for (let i = 0; i < workerNum - 1; i++) {
    distance.push(positions[i + 1] - positions[i])
  }
  distance = distance.sort() // distance有 workerNum - 1 项
  // 首先计算当前若不考虑最后一个工人种树数量，其余工人最多能种下多少树
  const total = distance.reduce((a, b) => a + b, 0)
  let lastindex = 0 // 记录上一次遍历是从哪个索引开始的
  for (let answer = Math.ceil(treeNum / workerNum); ; answer++) {
    let index = lastindex
    while (index < workerNum - 1 && distance[index] < answer) {
      index++
    }
    lastindex = index
    if (index >= workerNum - 1) {
      // 此时，说明每个工人种树数量已经超过了工人之间距离的最大值，故直接计算出每个工人要种树数量即可
      return treeNum - total
    } else {
      let tempTotal = 0
      for (let j = 0; j < index; j++) {
        tempTotal += distance[j]
      }
      // 如果此时，种树重叠了的工人种下的树，加上没有重叠的工人种下的树的总数，达到要求，就返回值
      if (tempTotal + (workerNum - index) * answer >= treeNum) {
        return answer
      }
    }
  }
}