二分答案模板题【详细解析】

这是二分答案的经典模板题，核心逻辑：锯片高度 H 越大 → 砍到的木材越少；H 越小 → 砍到的木材越多（满足严格单调性）。我们要找最大的 H，使得砍到的木材 ≥ M，直接用二分枚举所有可能的 H 即可。
完整步骤
1.输入数据：读取树木数量、需要的木材长度、每棵树的高度；
2.定二分范围：左边界l=1（最低高度），右边界r=最高树的高度（超过这个高度砍不到木材）；
二分枚举：
3.取中间值mid作为尝试的锯片高度；
4.用check函数判断：高度mid能否砍到足够的木材；
    满足条件 → 尝试更高的高度（记录当前 mid 为答案）；
    不满足条件 → 降低高度；
5.输出答案：最终记录的就是最大合法高度。

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e6 + 10;
int tree[MAXN];
int n, m;

// 核心判断函数：输入锯片高度x，判断能否砍到至少m米木材
// 二分答案题的核心就是修改这个check函数
bool check(int x){
    // 关键修正：必须用long long！
    // 木材总和最大可达4e11，int(最大2e9)会溢出，导致答案错误
    long long total = 0;
    // 遍历所有树
    for(int i = 1; i <= n; i++){
        // 如果树比锯片高，砍下多余的部分，累加到总木材
        if(tree[i] > x){
            total += tree[i] - x;
        }
    }
    // 总木材 ≥ 需要的m，返回true（满足条件）；否则false
    return total >= m;
} 

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> tree[i];
    }

    //找到所有树中最高的高度，作为二分的右边界r
    int max_height = 0;
    for(int i = 1; i <= n; i++) {
        max_height = max(max_height, tree[i]);
    }

    //  二分查找初始化
    // l：二分左边界（最低锯片高度）
    // r：二分右边界（最高树的高度，最高合法高度）
    // ans：记录最终答案（最大的合法锯片高度）
    int l = 1, r = max_height, ans = -1; 

    // 二分模板核心循环
    while(l <= r){
        // 取中间值mid，作为当前尝试的锯片高度
        int mid = (l + r) / 2;
        
        // 判断mid高度是否满足条件（能砍到足够木材）
        if(check(mid)){
            // ? 满足条件：可以尝试更高的高度！
            // 左边界右移，缩小范围
            l = mid + 1;
            // 记录当前mid为候选答案（因为我们要最大的H）
            ans = mid;
        }else{
            // ? 不满足条件：高度太高了，木材不够
            // 右边界左移，降低高度
            r = mid - 1;
        } 
    } 
    cout << ans;
    return 0;
}