/**
* 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);
剪树枝
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 活在钢筋水泥的大城市，偶尔能有一天休息只想在家苟延残喘。 浏览一下朋友圈朋友们秀出某名森林的风景，点上一个无奈的赞...
