Day 23 · 二分答案：把「求解」变成「判定」

题意：有一排树，高度各不相同。伐木机的锯片可以升到整数高度 H， 比 H 高的部分会被锯下来。要拿到至少 M 米木材，问锯片最高能升到多少？

思路

典型的 A 类（最大化）问题：答案 H 越大，砍到的木材越少。

check(H)：把每棵树超过 H 的部分加起来，看总数是不是 ≥ M。
这个函数从 H = 0 到 H = max(h) 的取值是「true…true…false…false」， 我们要最后一个 true 对应的 H。

所以用模板 A：可行就 ans = mid; l = mid + 1，不可行就 r = mid - 1。

4 7
20 15 10 17

15

5 20
4 42 40 26 46

36

完整代码

#include <iostream>
using namespace std;

int n;
long long m;                 // 需要的木材总量（可能到 2×10^9，必须 long long）
int h[1000005];              // 每棵树的高度，n 最大 10^6，数组开在全局

// check(H)：锯片升到高度 H 时，砍下的木材总量是否 >= m
bool check(long long H){
    long long sum = 0;
    for(int i = 0; i < n; i++){
        if(h[i] > H) sum += h[i] - H;   // 只有比 H 高的部分才被锯下来
        if(sum >= m) return true;       // 够了就提前返回：既加速又防止累加溢出
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);        // 关掉 cin/cout 与 scanf 的同步，读入更快
    cin.tie(0);
    cin >> n >> m;
    int maxh = 0;
    for(int i = 0; i < n; i++){
        cin >> h[i];
        if(h[i] > maxh) maxh = h[i];    // 顺路求出上界：最高的那棵树
    }

    // 答案（锯片高度）越大，砍到的木材越少 -> 单调，可以二分
    long long l = 0, r = maxh, ans = 0;
    while(l <= r){                      // 模板 A：ans 记录 + 区间跨越 mid
        long long mid = l + (r - l) / 2;
        if(check(mid)){                 // mid 可行，记下来，再试着锯更高
            ans = mid;
            l = mid + 1;
        } else {                        // mid 太高，木材不够，只能往低处找
            r = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

易错点

• 累加和不开 long long：10⁶ 棵树 × 4×10⁵ 高度，最坏能到 4×10¹¹，int 直接爆掉。 代码里用 sum >= m 提前 return 也是一种保护。
• 上界写成 10⁹ 之类的「想当然值」：树高最大只有 4×10⁵，上界取 max(h[i]) 最稳， 也顺便减少了二分层数。
• 把 check 的方向写反：记住「H 越高，木材越少」。如果不确定，就拿样例 2 手工验一个 H 值。
• N = 10⁶ 时用 cin 记得加 ios::sync_with_stdio(false)，不然读入会慢得明显。

题意：有 n 根原木，要切成 k 段等长的小段（长度必须是正整数，允许有剩余）。 问每段最长能有多长？如果连 1cm 的都切不出来，输出 0。

思路

也是 A 类：小段长度 len 越长，能切出的段数越少。

check(len)：Σ (L[i] / len) ≥ k 吗？这里的除法是整数除法， 天然就是「这根木头能切几段」，不用额外处理余数。

下界取 1（长度必须是正整数），上界取 max(L[i])。 如果 check(1) 都不成立，那 ans 一直是初值 0，正好输出 0 —— 初值选 0 是关键。

3 7
232
124
456

114

验算：232/114 = 2，124/114 = 1，456/114 = 4，合计 7 段 ✅；
如果 len = 115：232/115 = 2，124/115 = 1，456/115 = 3，合计 6 段 < 7 ❌ 所以答案就是 114。

完整代码

#include <iostream>
using namespace std;

int n;
long long k;                 // 需要的小段数量，最大 10^8
int L[100005];               // 每根原木的长度

// check(len)：所有原木都切成 len 厘米的小段，能不能凑够 k 段
bool check(long long len){
    long long cnt = 0;
    for(int i = 0; i < n; i++){
        cnt += L[i] / len;        // 整除：这根原木能切出几段
        if(cnt >= k) return true; // 够了就提前退出，后面不用再算
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    int maxl = 0;
    for(int i = 0; i < n; i++){
        cin >> L[i];
        if(L[i] > maxl) maxl = L[i];    // 上界：最长的那根原木
    }

    // len 越大，能切出的段数越少 -> 单调
    long long l = 1, r = maxl, ans = 0; // ★ ans 初值 0：切不出来时正好输出 0
    while(l <= r){
        long long mid = l + (r - l) / 2;
        if(check(mid)){                 // 能切够，记下来，再试试切更长
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;                // 切太长了，段数不够
        }
    }
    cout << ans << endl;
    return 0;
}

易错点

• ans 初值写成 -1：那样「切不出来」时会输出 -1，而题目要的是 0。
• 下界写 0：L[i] / 0 会直接除零崩溃（RE）。长度是正整数，下界就该是 1。
• 用 int 累加段数：n 最大 10⁵、每根最多切 10⁸ 段，累加过程可能超过 21 亿，用 long long。
• 不需要判断「余料怎么处理」—— 题目允许有剩余，整数除法天然处理了。

题意：把一个长度为 N 的正整数数列分成 M 段（每段必须连续）， 让「各段和中最大的那个」尽可能小，求这个最小值。

题面例子：4 2 4 5 1 分 3 段。
[4 2][4 5][1] → 段和 6、9、1，最大 9；
[4][2 4][5 1] → 段和 4、6、6，最大 6。最大值的最小可能值就是 6。

思路

这是今天第一道 B 类（最小化最大值）题，也是「二分答案 + 贪心」的经典组合。

我们二分的量是「允许的每段和上限 x」。check(x) 回答： 在每段和都不超过 x 的前提下，最少要分几段？如果这个段数 ≤ M，那 x 就可行。

「最少分几段」用贪心求：从前往后累加，一旦加上当前数就要超 x，就在这里切一刀。 这是最优的 —— 每一段都塞到装不下为止，段数自然最少。

上下界：l = max(Ai)（任何一段的和都不可能小于最大的单个数）， r = sum(Ai)（全部塞进一段，一定可行，满足模板 B 的前提）。

5 3
4 2 4 5 1

6

完整代码

#include <iostream>
using namespace std;

int n, m;
int a[100005];

// check(x)：限制「每段和都不超过 x」，最少要分成几段？段数 <= m 就算可行
bool check(long long x){
    int cnt = 1;             // 至少有一段
    long long cur = 0;       // 当前这一段已经累加的和
    for(int i = 0; i < n; i++){
        if(a[i] > x) return false;      // 一个数自己就超过 x，怎么分都不行
        if(cur + a[i] > x){             // 加上就爆了 -> 在这里切一刀
            cnt++;
            cur = a[i];
        } else {
            cur += a[i];                // 还能装得下，继续累加
        }
    }
    return cnt <= m;         // 用的段数不超过 m 就说明 x 可行
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    long long sum = 0, mx = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        sum += a[i];
        if(a[i] > mx) mx = a[i];
    }

    // 「最大值最小」：x 越大越容易可行 -> 单调，二分找最小的可行 x
    long long l = mx, r = sum;             // ★ r = sum 保证 check(r) 一定为真
    while(l < r){                          // 模板 B：while(l < r)
        long long mid = l + (r - l) / 2;   // 下取整，配合 r = mid 使用
        if(check(mid)) r = mid;            // 可行，试着更小
        else l = mid + 1;                  // 不可行，必须更大
    }
    cout << l << endl;                     // 结束时 l == r，就是最小的可行值
    return 0;
}

易错点

• 下界写成 0 或 1：A_i 可能比它大，会导致 check 永远返回 false，输出错误。要用 max(Ai)。
• 两个 while 循环条件搞混：模板 B 是 while(l < r)，不是 l <= r。 写成 <= 会多转一轮，可能输出越界的值。
• 模板 B 里把 r = mid 写成 r = mid - 1：那就变成模板 A 了， 而且最后没有 ans 记录，输出的是错误的值。收缩方式和「答案落在哪」必须配套。
• 贪心切段时忘了「不足以放下一个数就先切」，或者把 cur + a[i] > x 写成 >=： 题目要求「不超过 x」，等于 x 是合法的，所以必须用 >。

题意：一条长 L 的公路上原来有 N 个路标（起点、终点一定有）。 最多可以再增设 K 个路标（位置必须是整数）。定义「空旷指数」= 相邻路标间距的最大值。 问空旷指数最小能压到多少。

思路

典型的 B 类题：最小化「最大间距」。

二分「允许的最大间距 x」。check(x) 回答：要让所有相邻间距都 ≤ x， 最少要新增几块路标？总数 ≤ K 就可行。

★ 单段要插几块？推导一下

某两块的间距是 d。如果新插 c 块，就把 d 切成 c+1 段。 要让每一小段都 ≤ x，需要 d / (c+1) ≤ x，也就是 c ≥ d/x - 1。

因为 c 要是整数，所以最少的 c = ⌈d/x⌉ - 1。

而 ⌈d/x⌉ = (d-1)/x + 1（整数除法），所以：

cnt = (d - 1) / x;      // 一行搞定，整数除法自动下取整

上下界：l = 1（间距是整数，最小为 1），r = L（总长是任何间距的上限， 而且 x = L 时一块路标都不用加，必然可行 → 满足模板 B 的前提）。

101 2 1
0 101

51

只有起点 0 和终点 101 两块路标，可以加 1 块。
加在 50 处 → 间距 50、51，最大 51；加在 51 处 → 间距 51、50，最大 51。
想让最大间距到 50，就必须加 2 块（超预算），所以答案是 51。

完整代码

#include <iostream>
using namespace std;

int L, n, k;
int a[100005];               // 原有路标位置（输入保证递增）

// check(x)：想让所有相邻路标的间距都 <= x，最少要新增几块路标？<= k 就可行
bool check(long long x){
    long long need = 0;
    for(int i = 1; i < n; i++){
        long long d = a[i] - a[i - 1];      // 这一段原来的间距
        // 间距 d 用 cnt 块新路标切成 cnt+1 段，需要 d/(cnt+1) <= x
        // 所以 cnt = ceil(d/x) - 1 = (d-1)/x（整数除法自动下取整）
        need += (d - 1) / x;                // ★ 少写这个 -1 就会 WA
        if(need > k) return false;          // 已经超预算，不用再算了
    }
    return need <= k;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> L >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];

    // 「空旷指数」= 相邻路标的最大间距，我们要让它最小
    // x 越大越容易做到 -> 单调，二分最小的可行 x
    long long l = 1, r = L;              // ★ r = L 时一块都不用加，一定可行
    while(l < r){
        long long mid = l + (r - l) / 2;
        if(check(mid)) r = mid;          // 做得到，往更小的方向压
        else l = mid + 1;                // 做不到，只能放宽
    }
    cout << l << endl;
    return 0;
}

易错点

• (d-1)/x 写成 d/x：间距正好是 x 的倍数时会多算一块路标，导致答案偏大。
• 把「空旷指数」理解成间距之和或平均值：它是相邻间距的最大值，要最小化这个最大值。
• K = 0 的情况没考虑：此时答案就是原来最大的间距，二分必须能自然给出这个结果（我们 r = L、l = 1，没问题）。
• 路标位置是整数这一点决定了取整公式。如果题目允许实数的路标，公式就变成 ceil(d/x)-1 的另一套算法了 —— 看清「整数」二字。