算法基础：二分答案应用——木材加工与砍树

前言

二分答案是算法竞赛与笔试中极具技巧性的高分解法，核心思路是将复杂求解转化为简洁的二分 + 判定，专门解决「最大值最小」「最小值最大」等经典问题。本文从原理到实战，结合两道高频例题，带你从零掌握二分答案的核心逻辑与代码模板，轻松搞定同类题型。

一、二分答案

二分答案准确来说，应该叫做「二分答案 + 判断」。 二分答案可以处理大部分「最大值最小」以及「最小值最大」的问题。如果「解空间」在从小到大的「变化」过程中，「判断」答案的结果出现「二段性」，此时我们就可以「二分」这个「解空间」，通过「判断」，找出最优解。

二、二分答案经典算题

2.1 木材加工

2.1.1 题目

洛谷 P2440：木材加工

2.1.2 算法原理

2.1.3 代码

// 木材加工
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL a[N], n, k;

// 计算在切割长度为 x 情况下切几段
LL calc(LL x) {
    LL cnt = 0;
    for (int i = 1; i <= n; i++) cnt += a[i] / x;
    return cnt;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 0, r = 1e8;
    while (l < r) {
        LL mid = (l + r + 1) / 2;
        if (calc(mid) >= k) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
     ;
}