【算法/二分】luogu-P1873 [COCI 2011/2012

COCI 2011/2012 #5 经典题目，洛谷 P1873，是学习“二分答案（Binary Search on Answer）”必须掌握的教科书级经典例题。适合 GESP 五级、CSP-J 及算法初学者练习。题目难度⭐⭐☆☆☆，洛谷难度等级普及-。

P1873 [COCI 2011/2012 #5] EKO / 砍树

题目要求

题目描述

伐木工人 Mirko 需要砍 $M$ 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。

Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 $H$（米），伐木机升起一个巨大的锯片到高度 $H$，并锯掉所有树比 $H$ 高的部分（当然，树木不高于 $H$ 米的部分保持不变）。Mirko 就得到树木被锯下的部分。

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

Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 $H$，使得他能得到的木材至少为 $M$ 米。换句话说，如果再升高 $1$ 米，他将得不到 $M$ 米木材。

输入格式

第 $1$ 行 $2$ 个整数 $N$ 和 $M$，$N$ 表示树木的数量，$M$ 表示需要的木材总长度。

第 $2$ 行 $N$ 个整数表示每棵树的高度。

输出格式

$1$ 个整数，表示锯片的最高高度。

输入输出样例 #1

输入 #1

4 7
20 15 10 17

输出 #1

15

输入输出样例 #2

输入 #2

5 20
4 42 40 26 46

输出 #2

36

说明/提示

对于 $100\%$ 的测试数据，$1\le N\le10^6$，$1\le M\le2\times10^9$，树的高度 $\le 4\times 10^5$（部分强化数据中树高可达 $10^9$），所有树的高度总和 $>M$。

题目分析

本题属于经典的**二分答案（Binary Search on Answer）**问题。

1. 为什么不能暴力枚举？

题目要求我们寻找伐木机锯片的最大高度 $H$。

如果我们从 $0$ 开始逐个枚举高度 $H$（或者从树木的最大高度从大往小枚举），每枚举一个高度，都需要遍历这 $N$ 棵树来累加获得的木材总量：

$f(H) = \sum_{i=1}^N \max(0, \text{tree}[i] - H)$

• 树木数量 $N \le 10^6$；
• 树木高度最大可达 $4\times 10^5$（甚至 $10^9$）；
• 暴力枚举的总计算次数为 $O(N \times \max H_i) \approx 10^6 \times 4\times 10^5 = 4 \times 10^{11}$ 次，计算机 1 秒通常只能处理 $10^8$ 次左右的基本运算，因此暴力枚举必然导致超时（TLE）。

2. 函数的单调性分析

我们观察锯片高度 $H$ 与砍下的木材总量 $f(H)$ 之间的关系：

• 锯片升得越高（$H$ 增大）：每棵树被锯下的部分就会减少或不变，因此最终收集到的总木材量就会减少；
• 锯片降得越低（$H$ 减小）：每棵树被锯下的部分就会增加或不变，因此最终收集到的总木材量就会增多。

因此，$f(H)$ 是关于 $H$ 的单调不增函数。

当我们检查“在高度 $H$ 下，得到的木材量是否不少于 $M$（即 $f(H) \ge M$）”时，判定结果呈现明显的单调分界：

题目要求的是“满足条件的最大的整数高度 $H$”，正好对应最后一个返回 true 的分界点！

只要一个解空间满足这种单调性，我们就可以使用二分答案，将“求最值”转化为“猜答案 + 判定（Check）”，将线性的逐个排查降维成对数级的二分折半收敛！

解题步骤与核心细节

1. 确定二分区间的上下界

• 下界 $L$：$L = 0$。极端情况下，即使把锯片贴在地面（$H=0$）把树齐根锯掉，也是合法的操作。
• 上界 $R$：$R = \max(\text{tree}[i])$。锯片的高度显然不可能超过森林中最高的树的高度，因为超过最高树木后，一米木材也锯不到。

2. 编写判定函数 check(H)

对于候选高度 $H$，遍历 $N$ 棵树：

• 如果树高 $\text{tree}[i] > H$，则将多出的部分 $(\text{tree}[i] - H)$ 累加进 sum；
• 如果树高 $\text{tree}[i] \le H$，则无法提供木材，跳过。
• 判断最终累加得到的 sum 是否 $\ge M$。

⚠️ 核心避坑点（必看）：整型溢出
题目中 $M \le 2 \times 10^9$，$N \le 10^6$，树高最大可达 $4\times 10^5 \sim 10^9$。
如果在 $H = 0$ 附近，累加和 sum 最大可达 $10^6 \times 10^9 = 10^{15}$，这远远超过了 32 位有符号整型 int 的最大表示范围（$2^{31}-1 \approx 2.14 \times 10^9$）。
如果 sum 使用 int，会直接溢出变成负数，从而导致判定函数返回 false，得出完全错误的答案！因此，累加和 sum 以及木材需求量 $M$ 必须定义为 64 位整型 long long。

3. 常数优化小技巧

在 check(H) 函数内部累加时，并不需要傻傻地把所有树都加完。只要在循环过程中发现当前的 sum >= M，就可以立即提前返回 true。这一步剪枝可以在测试数据中减少大量无谓的累加计算。

4. 二分收敛过程

采用经典的左闭右闭区间 [l, r] 二分模板：

long long l = 0, r = max_val;
long long ans = 0;
while (l <= r) {
    long long mid = l + (r - l) / 2;
    if (check(mid)) {
        ans = mid;     // mid 高度符合要求，记录下当前可行答案
        l = mid + 1;   // 尝试寻找更高的锯片高度
    } else {
        r = mid - 1;   // mid 高度切出来的木材不够，必须降低锯片
    }
}

完整参考代码 (C++)

/**
 * Problem: luogu P1873 [COCI 2011/2012 #5] EKO / 砍树
 * Algorithm: 二分答案 (Binary Search on Answer)
 * Author: OneCoder
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 树木数量最大为 10^6
const int MAXN = 1000005;
int trees[MAXN];
int n;
long long m;

/**
 * @brief 判定函数：检查锯片设定在高度 mid 时，能否锯出至少 m 米木材
 * @param mid 猜测的锯片高度
 * @return true 表示能够得到至少 m 米木材；false 表示木材不足
 */
bool check(int mid) {
    long long sum = 0; // 必须使用 long long 累加，防止溢出
    for (int i = 0; i < n; i++) {
        if (trees[i] > mid) {
            sum += (trees[i] - mid);
            // 贪心剪枝：一旦满足所需木材量，立刻提前返回，提高常数效率
            if (sum >= m) {
                return true;
            }
        }
    }
    return sum >= m;
}

int main() {
    // 针对百万级输入规模开启 IO 流加速
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) {
        return 0;
    }

    int max_val = 0;
    for (int i = 0; i < n; i++) {
        cin >> trees[i];
        if (trees[i] > max_val) {
            max_val = trees[i];
        }
    }

    // 二分区间：高度下界为 0，上界为最高树的高度
    int l = 0, r = max_val;
    int ans = 0;

    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;     // 当前高度可行，记录最优解
            l = mid + 1;   // 贪心尝试更高的锯片高度
        } else {
            r = mid - 1;   // 木材不够，锯片过高，向左半区间收缩
        }
    }

    cout << ans << "\n";

    return 0;
}

复杂度分析

• 时间复杂度：
  • 二分区间长度为 $\max(H_i)$，在最坏情况下二分查找需要执行 $\log_2(\max H_i)$ 次。
  • 当树高达到 $10^9$ 级别时，$\log_2(10^9) \approx 30$ 次；若树高在 $4\times 10^5$ 级别时，$\log_2(4\times 10^5) \approx 19$ 次。
  • 每次判定函数 check 遍历一次 $N$ 棵树，耗时 $O(N)$。
  • 因此总时间复杂度为 $\mathcal{O}(N \log (\max H_i))$。代入 $N = 10^6$，总基本运算次数约在 $2\times 10^7$ 次左右，配合 I/O 加速与提前剪枝，耗时仅需约 100~200ms，在 1.0 秒时限内绰绰有余。
• 空间复杂度：
  • 仅使用了一个大小为 $10^6$ 的全局 int 数组存储树高，内存消耗约为 $4\text{ MB}$，远低于题目常见的 $128\text{ MB} \sim 256\text{ MB}$ 空间限制，空间复杂度为 $\mathcal{O}(N)$。

总结与同类拓展

二分答案是算法竞赛与考级中最核心的“解题模式”之一。当你遇到以下特征的问题时，应第一时间联想到二分答案：

1. 问题要求**“求最大值的最小值”或“求最小值的最大值”**；
2. 直接构造最优解或者动态规划非常困难，但给定一个具体答案后，写出验证函数 check() 却极其直观简单；
3. 答案的可行性具备明显的单调性质（即随着参数增大，条件从成立逐渐变为不成立，或反之）。

经典同类推荐练习题：

• luogu-P2440 木材加工（几乎同源的经典木材切分模型）
• luogu-P2678 [NOIP 2015] 跳石头（最小值最大化 + 贪心跳跃验证）
• luogu-P1182 数列分段 Section II（最大值最小化模型）
• luogu-P1824 进击的奶牛（经典的距离最大化问题）