C++二分答案思想

猜答案的艺术：C++二分答案思想详解

什么是二分答案？

想象一下，你正在玩一个“猜价格”游戏：主持人说一个商品的价格在1到100元之间，你每次猜一个数，他会告诉你“高了”还是“低了”。你每次都猜中间的数，比如先猜50，如果高了就猜25，如果低了就猜75……很快就能猜中。这就是二分查找的思路。

但有些问题更奇妙——我们不是直接在一个有序数组里找一个数，而是要猜一个“可行”的答案，并且这个答案要满足某些条件。比如：你有一根很长的绳子，想把它剪成若干段相同长度的小绳子，每段长度必须是整数，最多能剪成多少段？反过来，如果要求剪出固定段数，那么每段最长可以是多少？

类似的问题在生活中很常见：

分蛋糕：一块大蛋糕（比如长30厘米），想要分给10个小朋友，每人分到一样长的一小块（整数厘米），那么每块最长可以是多少？如果每块太长，分不到10块；太短则浪费。
零花钱：妈妈给你100元，要求你每天花一样多的钱（整数元），想花10天，那么每天最多花多少元？如果你每天花12元，10天就是120元，超了；如果每天花8元，10天80元，还剩20元可以多花几天？其实这是“最少天数”问题。

这些问题的共同点：答案（每段长度、每天花费等）通常在一个范围内，并且随着答案变大，它的“可行性”会改变（比如绳子段数变少、能花的天数变少）。我们可以用类似猜数字的方法，每次取中间值，然后检查它是否可行，如果可行就试试更大的值，否则就试试更小的值。这种方法叫做二分答案。

二分答案的核心是检查函数（check），它用来判断一个候选答案是否满足题目要求。只要检查函数写对，整个问题的求解就变得简单高效。

二分答案解决什么问题？

二分答案专门用来解决最优化问题，尤其是那些答案有单调性的问题。什么叫单调性？就是：如果答案x可行，那么比x小的答案通常也可行（或者反过来），形成一个单调的“可行”与“不可行”的分界点。比如切木头问题：长度越长，可切出的段数越少。所以存在一个临界长度ans，使得长度≤ans时都能切出至少k段（可行），长度> ans时切不出（不可行）。我们就是要找这个最大的可行长度。

常见的题型有：

最小值最大化：比如“求每段最小长度（在满足条件下）的最大值”
最大值最小化：比如“求每段最大长度（在满足条件下）的最小值”

只要问题的答案有明确的上下界，并且能写出check(x)判断是否可行，就可以用二分答案。

举个具体例子：切木头问题

题目：有n根木头，长度分别是a[0]到a[n-1]。现在要把它们切成k段长度相同的小木头（每段必须是整数长度，可以浪费一些）。请问小木头的最大可能长度是多少？

比如木头长度：[10, 15, 8, 20]，要切出5段。每段最长应该是多少？

我们来分析：如果每段长度是1，那切成段数 = 10+15+8+20 = 53段，远大于5段，可行。如果每段长度是20，只有20那根能切出1段，其他切不出，总段数=1 < 5，不可行。所以答案在1到20之间。

我们可以用二分答案：可能的长度范围是1到最长木头（20）。每次取中间长度mid，检查把每根木头能切出多少段（比如10米木头能切出 10 / mid 段），加起来看是否 >= k。如果 >= k，说明mid可行，可以试试更大的长度；否则mid太大，要减小。

为什么这样检查？ 因为每根木头切成长度为mid的小段，最多能切 a[i] / mid 段（整除，不能拼接浪费）。总段数 >= k 则说明这个长度可行。而且这个检查是整数运算，很简单。

代码实现

下面是一段完整的C++代码，包含输入输出和注释，可以直接运行。

#include <iostream>
using namespace std;

int a[100]; // 存储每根木头的长度
int n;      // 木头数量
int k;      // 目标段数

// 检查函数：每段长度为len时，能否至少切出k段？
bool check(int len) {
    if (len == 0) return false; // 长度不能为0
    int total = 0; // 能切出的总段数
    for (int i = 0; i < n; i++) {
        total += a[i] / len;    // 每根木头能切出的段数（整数除法）
    }
    return total >= k;          // 如果总段数达到要求，返回true
}

int main() {
    // 手动输入数据（你也可以改成从键盘读取）
    n = 4;
    k = 5;
    a[0] = 10; 
    a[1] = 15; 
    a[2] = 8; 
    a[3] = 20;

    int left = 1;               // 答案下界（最小长度1）
    int right = 20;             // 答案上界（最长木头长度）
    int ans = 0;                // 存储最终答案

    while (left <= right) {     // 闭区间二分
        int mid = left + (right - left) / 2; // 防止溢出
        if (check(mid)) {
            ans = mid;          // 当前mid可行，记录下来
            left = mid + 1;     // 尝试更大的长度（右移左边界）
        } else {
            right = mid - 1;    // mid太大，缩小右边界
        }
    }

    cout << "最大长度是: " << ans << endl;
    return 0;
}

运行结果：最大长度是5。因为10米可以切2段5米，15米切3段，8米切1段，20米切4段，总段数 = 2+3+1+4 = 10段 ≥ 5段。如果取6米呢？10切1段，15切2段，8切1段，20切3段，总段数 = 7段 ≥ 5段，也满足，但还能更大吗？取7米：10切1，15切2，8切1，20切2，总=6段；取8米：10切1，15切1，8切1，20切2，总=5段，刚好满足。取9米：10切1，15切1，8切0，20切2，总=4段 < 5，不可行。所以最大可行长度是8？等一下，我们代码跑出来是5？我重新算一下：10/5=2, 15/5=3, 8/5=1, 20/5=4，总和=10。但题目要求是至少切出5段，所以5可行。但8也可行（10/8=1,15/8=1,8/8=1,20/8=2，总和=5）。那为什么没找到8？因为我们初始right设成了20，但二分查找会一直找到最大的可行值。实际上代码应该找到8才对，让我们检查一下逻辑：left=1, right=20。mid=10，check(10)：10/10=1,15/10=1,8/10=0,20/10=2，总和=4<5 → false，right=9。mid=5，check(5):10/5=2,15/5=3,8/5=1,20/5=4，总和=10≥5 → true，ans=5,left=6。mid=(6+9)/2=7，check(7):10/7=1,15/7=2,8/7=1,20/7=2，总和=6≥5 → true，ans=7,left=8。mid=(8+9)/2=8，check(8):总和=5≥5 → true，ans=8,left=9。mid=(9+9)/2=9，check(9):总和=4<5 → false，right=8。此时left=9>right=8，退出循环，ans=8。所以最终答案是8。我之前的计算错了，代码正确会输出8。说明二分答案能准确找到最大值。

新手容易犯的错误

边界条件搞错：二分答案的初始left和right要确保覆盖所有可能的答案。比如木头长度最小是1（长度必须整数），最大是所有木头中最长的。如果left从0开始，注意除以0会崩溃。有些题目下界可能是0，但检查时要处理。
检查函数写反：一定要想清楚“可行”的条件是什么。例如切木头问题是总段数 ≥ k，而有些问题是总段数 ≤ k（比如分配任务，要求每段尽量长但不超过特定段数）。仔细读题。
mid计算溢出：(left+right)/2在int范围内一般安全，但为了保险推荐 left + (right - left) / 2，特别是当left和right很大时。
死循环：二分答案通常在整数范围用闭区间while (left <= right)，每次更新left=mid+1或right=mid-1，一定退出。如果用了while (left < right)且更新为left=mid或right=mid，可能死循环。建议初学者统一用闭区间+±1的方式。
没有记录答案：有些写法只在check(mid)为true时更新ans，最后输出ans。如果忘了记录，最后输出left或right可能导致错误（取决于退出条件）。最好用一个变量存储可行答案。

完整示例：分零食问题

再来看一个贴近生活的例子：班级聚会，薯片、饼干、巧克力等零食混合在一起，总长度（或总数量）是固定的。要求平均分给m个小朋友，每人得到连续的一长段（比如每段由同一种零食组成，但这里简化成可以任意切分）。每段必须是整数长度，可以浪费。求每人最多能分到多少长度？

实际上和切木头是一样的，只是把“木头”换成“零食”。代码几乎不用改。

另一个例子：猜价格升级版。你有一个数字范围[L,R]，要找一个最大的整数x，使得“能够用x元买下某样商品”即满足某种条件。比如你有100元，要买若干件单价相同的商品，每件价格是整数，至少买10件，那么最多每件多少钱？用二分答案：最低1元，最高100元，检查总价=价格*10 ≤ 100，找到最大的价格。

总结

二分答案是一种强大的解题思想，能把最优化问题转化为判断问题。关键在于：

确定答案的范围（上下界）
写出正确的check函数
选择合适的二分模板（闭区间、左闭右开等）

掌握了它，很多“最大值最小”或“最小值最大”的难题都能迎刃而解。下次遇到类似的问题，先想想：答案有范围吗？能写check吗？如果能，就大胆用二分答案吧！