砍树:选砍伐高度使木材量不少于目标且最接近
哪些公司问过
答案要点
- 木材量随砍伐高度 h 单调不增,可对 h 二分
- 二分区间 [0, max(树高)],找木材量 ≥ target 的最大 h
- 每次检查 Σmax(0, tree−h),总复杂度 O(n log H)
- 累加和用 64 位整型防溢出,并提前判断无解
易错点
- 二分方向写反,找成了满足条件的最小 h
- 累加木材量用 int 导致溢出
- 没处理全部砍光也不够 target 的情况
面试官常见追问
- 为什么要找最大的 h 而不是最小的?
- 如果要求木材量最接近 target、允许小于呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。