面试题库 › C++ / 后端 › 砍树:选砍伐高度使木材量不少于目标且最接近

砍树:选砍伐高度使木材量不少于目标且最接近

难度 ★★☆在 1 场真实面经中被问到 方向:C++ / 后端考点:查找算法

哪些公司问过

微软1

常见岗位:软件开发(未写技术栈)

答案要点

  1. 木材量随砍伐高度 h 单调不增,可对 h 二分
  2. 二分区间 [0, max(树高)],找木材量 ≥ target 的最大 h
  3. 每次检查 Σmax(0, tree−h),总复杂度 O(n log H)
  4. 累加和用 64 位整型防溢出,并提前判断无解

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题