二分答案练习

题目：有若干根木头，要切出至少 $n$ 段等长的小段，问每段最长能多长（长度取整）。

单调性：每段越短，能切出的段数越多，越容易凑够 $n$ 段；越长越难。所以「能切够 $n$ 段」关于段长是单调的——存在一个临界长度，比它短都可行、比它长都不行。我们要求的正是这个临界的最大长度，典型的二分答案。

答案范围：最短 1，最长是最长的那根木头 maxLen。

// wood[] 是每根木头长度
bool check(int len) {           // 段长 len 能否切出 >= n 段
    long long cnt = 0;
    for (int w : wood) cnt += w / len;  // 每根能切多少段
    return cnt >= n;
}
int l = 1, r = maxLen, ans = 0;
while (l <= r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) { ans = mid; l = mid + 1; }  // 够，试更长
    else r = mid - 1;
}

复杂度 $O(k\log (\text{maxLen}))$，$k$ 是木头根数。坑：（1）cnt 用 long long，段数可能很大会爆 int；（2）len 从 1 起，别让除数为 0；（3）求最大长度，check 通过要往大试。