二分答案模板题

这道题是二分答案（最大值最小化）的经典模板题，和砍树题逻辑完全同源，核心特征：
我们要找最小的段和最大值，这个值满足单调性：设定的最大值越大 → 需要分的段数越少；设定的最大值越小 → 需要分的段数越多。
[完整步骤]
1.确定二分范围（最关键）：
2.左边界 l = 数组中最大的数（每段至少要装下最大的数，不可能更小）
3.右边界 r = 数组所有数的总和（整个数组不分一段，最大值就是总和）
4.二分枚举答案：取中间值 mid 作为「假设的段和最大值」
    check 函数判断：计算用 mid 做最大值，最少需要分几段
        分段数 ≤ M：mid 合法，尝试更小的最大值（缩小右边界）
        分段数 > M：mid 太小，需要更大的最大值（扩大左边界）
5.记录答案：最终的 ans 就是满足条件的最小最大值

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

// 核心check函数：输入假设的最大段和x，判断能否分成<=m段
// 返回值：true=可以满足要求，false=不满足
int check(int x){
    // ?? 关键：sum必须用long long！
    // 元素最大1e8，长度1e5，总和最大1e13，int会溢出导致答案错误
    long long sum = 0;   // 当前分段的和
    int cnt = 1;         // 分段数量，初始为1（至少有一段）
    
    // 遍历整个数列
    for(int i = 0; i < n; i++){
        // 如果当前段加上a[i]不超过最大值x，就加入当前段
        if(sum + a[i] <= x){
            sum += a[i];
        }
        // 超过了，就新开一段，当前段从a[i]开始
        else{
            sum = a[i];
            cnt++;  // 分段数+1
        }
    }
    // 最终分段数<=m，说明x这个值可行
    return cnt <= m;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }	
    // 初始化二分边界（核心！）
    int l = -1, r = 0;
    // 左边界l：数组最大值（每段必须装下最大的数）
    // 右边界r：数组总和（不分段时的最大值）
    for(int i = 0; i < n; i++){
        l = max(l, a[i]);
        r += a[i];
    }
    //二分查找核心模板
    while(l <= r){
        // 计算中间值，作为当前尝试的最大段和
        int mid = (l + r) / 2;
        
        // 判断mid是否可行
        if(check(mid)){
            // ? 可行：尝试更小的最大值（缩小右边界）
            r = mid - 1;
            // 记录当前mid为候选答案（我们要最小的最大值）
            ans = mid;
        }else{
            // ? 不可行：需要更大的最大值（扩大左边界）
            l = mid + 1;
        }
    }
    cout << ans; 
    return 0;
}
//Tian