CJBS04｜木料等长切割 题解

核心算法

二分答案，寻找最大的可行段长。

思路推导

给定段长 $L>0$，第 $i$ 根木料能提供 $\lfloor a_i/L\rfloor$ 段。若总段数至少为 $k$，则 $L$ 可行；更短的长度也一定可行。可行性随 $L$ 增大呈“真到假”的单调变化。

维护 left 为可行值、right 为不可行值。初始 left=0，right=max(a)+1，不断用中点缩小边界。

正确性说明

由于任意可行长度的更小值也可行，答案集合是连续整数区间 $[0,answer]$。循环始终保持 left 可行、right 不可行；结束时二者相邻，因此 left 正是最大的可行整数。

复杂度

• 每次检查：$O(n)$；
• 二分次数：$O(\log \max a_i)$；
• 总时间：$O(n\log \max a_i)$；
• 额外空间：$O(1)$。

易错点

• mid=0 时不能做除法，因此只在 left+1<right 时取正中点；
• 段数之和可能很大，应使用 long long 并在达到 $k$ 后提前停止；
• 题目要求“至少 $k$ 段”，多切出的段不影响可行性；
• 不可行时答案为 0。