1271 砍伐树木cuttree命题人 外部导入时间限制 1000 sec 内存限制 128 MB题目描述 小华被大林叫去砍树他需要砍倒m米长的木材。现在小华弄到了一个奇怪的伐木机。伐木机工作过程如下小华设置一个高度参数h米伐木机升起一个巨大的锯片到高度h并锯掉所有的树比h高的部分当然树木不高于h米的部分保持不变。小华就得到树木被锯下的部分。例如如果一行树的高度分别为20、15、10

思路： 要找到伐木机锯片的最大高度h，使得得到的木材至少为m米。可以使用二分查找的方法来解决。

首先，确定二分查找的上下界。上界初始化为树木的最大高度，下界初始化为0。

然后，每次取上下界的中间值mid作为锯片的高度，计算锯掉的木材长度。如果锯掉的木材长度大于等于m，则说明锯片的高度可以再增加，将下界更新为mid；否则，说明锯片的高度需要减小，将上界更新为mid。

最后，当上界和下界相等时，说明找到了最大的锯片高度。输出上界即可。

时间复杂度分析：二分查找的时间复杂度为O(logn)。而计算锯掉的木材长度需要遍历n棵树，时间复杂度为O(n)。所以，总的时间复杂度为O(nlogn)。

具体实现见下面的代码：