剪树枝

/**
 * NOTE: 有一条马路，马路上有很多树，树的高度不一。现在要统一剪树，剪到高度为 h。
 * 意思就是，比 h 高的树都剪到 h，比 h 低的树高度不变。
 * 所有的树剪掉的总长度为 C。 现在要使 C > 某个值的情况下(假设为 MM)，使 h 最大。问怎么确定 h。
 */

// NOTE: 树枝
const tree = [10, 3, 2, 21, 8, 19, 7, 11]

/**
 *
 * @param {树枝的集合} tree
 * @param {剪树枝的总长度} c
 * @param {每次剪多长} range
 */
function cutTree(tree, c, range) {
  if (tree.length === 0) {
    return 0
  }
  let start = 0
  let end = Math.max(...tree)
  while (start <= end) {
    // 每次都取中间
    const mid = start + ((end - start) >> 1)
    // console.log(mid)
    let h = 0
    for (let i = 0; i < tree.length; i++) {
      // 挑选出大于 mid 的数
      if (tree[i] > mid) {
        h = h + tree[i] - mid
      }
    }
    if (h > c) {
      if (h - c <= range) {
        return mid
      }
      // 剪 range
      end = end - range
    } else {
      start = start + range
    }
  }
  return -1;
}

const res = cutTree(tree, 12, 1)
console.log(res)

const a = cutTree([10, 8, 9, 7, 7, 6], 16, 1);
const b = cutTree([10, 8, 9, 7, 7, 6], 20, 1);
const c = cutTree([10, 8, 9, 7, 7, 6], 15, 1);

// console.log(a, b, c);