木头分段数动画演示
拖动木头长度 L,观察“能分成的段数”如何变化,理解二分单调性
1. 输入数据并调节长度 L
原木长度(空格分隔)
8 5 10 13 7 15
目标段数 k
当前长度 L
更新画面
L - 1
L + 1
自动播放
默认示例
原木根数 n
0
当前长度 L
0
总段数
0
是否满足 ≥ k
否
2. 卡通原木分段动画
3. 当前讲解
正在等待计算…
总段数 = Σ floor(木头长度 / L)
L 变大,段数会怎样?
左边:L 小 → 能切出更多段
右边:L 大 → 能切出更少段
结论:当 L 变大时,段数不会变多,所以满足二分单调性。
判断函数:设 f(L) = 能切出的总段数,如果 f(L) ≥ k,说明这个 L 还可以尝试更大。
因为 L 越大,每根木头的 floor(a[i] / L) 只会不变或变小,所以总段数单调不增。
因此可以二分答案,求“最大的满足 f(L) ≥ k 的 L”。