1271: 砍伐树木 (cuttree) - 二分查找算法详解

本题要求找到砍伐树木的最高高度，使得砍伐得到的木材至少为 m 米。使用二分查找算法，快速高效地找到答案。

题目描述

小华被大林叫去砍树，他需要砍倒 m 米长的木材。现在，小华弄到了一个奇怪的伐木机。伐木机工作过程如下: 小华设置一个高度参数 h (米), 伐木机升起一个巨大的锯片到高度 h, 并锯掉所有的树比 h 高的部分 (当然，树木不高于 h 米的部分保持不变)。小华就得到树木被锯下的部分。

例如, 如果一行树的高度分别为 20、15、10 和 17 米, 小华把锯片升到 15 米的高度, 切割后树木剩下的高度将是 15、15、10 和 15 米，而小华将从第 1 棵树得到 5 米, 从第 4 棵树得到 2 米，共得到 7 米木材。

小华非常关注生态保护, 所以他不会砍掉过多的木材。这正是他为什么要尽可能高地设定伐木机锯片的原因。帮助小华找到伐木机锯片的最大的整数高度 h, 使得他能得到的木材至少为 m 米。换句话说, 如果再升高 1 米，则他将得不到 m 米木材。

输入

第 1 行 2 个整数 n 和 m, n 表示树木的数量, m 表示需要的木材总长度。

第 2 行 n 个整数, 表示每棵树的高度, 值均不超过 10⁹。保证所有木材长度之和大于 m, 因此必然有解。

输出

一行一个整数，表示砍树的最高高度。

样例输入

5 20
4 42 40 26 46

样例输出

思路

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

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

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

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

时间复杂度分析

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

具体实现

```cpp #include #include using namespace std;

int main() { int n, m; cin >> n >> m; int trees[n]; for (int i = 0; i < n; i++) { cin >> trees[i]; }

int left = 0, right = *max_element(trees, trees + n);
int ans = 0;
while (left <= right) {
    int mid = (left + right) / 2;
    long long total = 0;
    for (int i = 0; i < n; i++) {
        if (trees[i] > mid) {
            total += trees[i] - mid;
        }
    }
    if (total >= m) {
        ans = mid;
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
cout << ans << endl;
return 0;

}