猜答案的艺术：如何用二分答案轻松解决“最大最小”难题

你有没有遇到过这种情况——明明答案就躺在一个范围内，但你盯着题目却不知道从哪下手？比如分蛋糕，要分给10个小朋友，每人得整数厘米，每块最长能有多少？你从1试到30，挨个检查，最后找出了最大可行值，但考试时时间不够啊。其实，这种“猜答案”的事，完全可以用一种优雅的方式来做，就像我们玩“猜价格”游戏一样。

从猜价格游戏说起

想象一下，主持人对你说：“这件商品价格在1到100之间，你猜一个数，我会告诉你高了还是低了。”你会怎么猜？肯定不是从1开始一个个试，而是先猜50。如果高了，就猜25；如果低了，就猜75。每次排除一半的可能性，最多7次就能锁定。这就是二分查找。

但有些问题，我们不是在一个有序数组里找某个具体数，而是要猜一个“可行”的答案。比如切木头：有一堆长短不一的木头，想切成若干段长度相等的小段，问每段最长能切多长？答案就在1到最长木头长度之间，而且答案越大，能切出的段数就越少。这种“答案越大，可行性越差（或越好）”的单调性，正是二分答案的用武之地。

核心：check函数——可行性判断

二分答案的思想非常简单：

1. 确定答案的上下界。
2. 取中间值 mid，让后写一个 check(mid) 函数，判断这个答案是否可行。
3. 如果可行，就朝“更优”的方向继续猜；否则往反方向猜。
4. 直到边界收敛，得到最优解。

这里最关键的不是二分本身，而是**check函数的正确性**。只要check写对，整个问题就解决了一大半。

拿切木头来说，check(len)的逻辑就是：把每根木头按长度len能切出的段数加起来，看是否大于等于目标段数k。比如木头长度是a[i]，那么它能贡献的段数就是a[i] / len（整数除法）。

bool check(int len) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += a[i] / len;
    }
    return total >= k;
}

然后二分区间[1, maxLen]，闭区间套模板：

int left = 1, right = maxLen, ans = 0;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (check(mid)) {
        ans = mid;
        left = mid + 1;   // 尝试更大的长度
    } else {
        right = mid - 1;  // 太大，缩小
    }
}

这个模板几乎是所有二分答案题的通用骨架。为什么在check为真时记录ans？因为我们要的是最大可行值，所以每次可行都暂存，最后输出的一定是最优解。如果不记录，直接输出left或right，很容易因边界差异出现差1错误——新手最常见的坑。

假币问题：二分答案的另一副面孔

有一种题型，表面上看不出“答案有范围”，但仔细一想，完全可以用二分答案。比如“假币问题”：有n枚硬币，其中一枚比真币轻，给你一架天平但没刻度，最少称几次一定能找出假币？

这个问题的答案——称量次数——显然是一个整数，而且范围在0到某个上界之间。更关键的是它满足单调性：如果称3次能保证找到，那么称4次当然也能。所以我们可以二分答案次数mid，然后判断mid次称量最多能在多少枚硬币中找出假币。

那check(mid)怎么写？每一次称量，天平有三种结果：左重、右重、平衡。因此一次称量最多能把硬币分成3组，假币一定在其中一组里。所以称mid次，最多能覆盖3^mid枚硬币。如果3^mid >= n，说明mid次可行。

bool check(int times) {
    long long covered = 1;
    for (int i = 0; i < times; i++) covered *= 3;
    return covered >= n;
}

然后二分次数区间[0, n]（实际最多几十次），每次跑一下check，瞬间得到答案。这个过程让我最着迷的地方是：你根本不需要设计具体的称法，只通过“一次称量最多三种结果”这个客观规律，就足以证明可行性。这就是二分答案的威力——把复杂的最优化问题，降维成一个简单的判定问题。

当然，假币问题还有一个经典的递推解法，但用二分答案来想，思路会开阔很多。当你看到一个“最少多少次”的题目，先别急着递推，试着把“次数”当作答案去二分，往往能豁然开朗。

别把二分查找和二分答案混为一谈

还有一个很容易混淆的点，值得单独说一说。比如“和为给定数”这个问题：给你n个整数，问是否存在两个数的和等于m。有的同学一看到“查找”，就脱口而出“二分答案”。停下来想一想，这真的是二分答案吗？

不是。它是在一个已知集合中查找是否存在某个数对，而不是在一个连续答案区间上猜答案。正确的做法是：排序，然后用双指针从两端向中间扫描，或者固定一个数，二分查找另一个数。这属于二分查找的应用，虽然二者共享“二分”这个词，但思考路径完全不同。

区分它们，有一个简单标准：答案本身是否在某个区间内，且需要你通过check函数去逼近？ 如果是，就是二分答案；如果不是，只是在已有数据里快速定位，那就是二分查找。很多初学者栽在“逢二分就套模板”上，就是因为没搞清楚自己到底在二分什么。

单调性——二分答案的命根子

前面反复提到“单调性”，这是二分答案成立的前提。用数学一点的话说：如果mid是可行的，那么所有比它“更优”的值也一定可行。例如切木头长度越短，切出的段数越多，所以“越短越可行”，存在一个临界值，左侧可行右侧不可行（或反之）。

但并不是所有问题都有这种单调性。比如“求一组数据的平均值”，你没法说“平均值越大越可行”，因为没有可行性这个概念。如果你发现某个最优化问题，无论答案怎么变，可行性都是随机跳跃的，那二分答案绝对帮不了你。

推荐模板和注意事项

最后，给你一个我觉得最不会出错的模板，闭区间+ans记录：

int l = 下界, r = 上界, ans = 下界;
while (l <= r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) {
        ans = mid;
        l = mid + 1;   // 找最大可行解
        // 如果找最小可行解，改成 r = mid - 1; ans = mid;
    } else {
        r = mid - 1;   // 反之则 l = mid + 1
    }
}

几点提醒：

• 上界不要随便设，比如切木头中上界是maxLen，而不是10^9，否则可能多几次循环，但一般没问题。关键是确保答案落在区间内。
• mid计算用l + (r - l) / 2，避免l+r溢出。
• 如果下界是0，注意check里可能除以0，比如a[i]/len，要特判len==0。
• 如果题目要求实数答案，比如“最多能分到多少长度的蛋糕且可以是小数”，二分时用while(r - l > eps)循环，但模板思想完全一样。

写在最后

二分答案之所以迷人，是因为它把“寻找最优解”这个看似需要疯狂枚举或巧妙构造的问题，转化为“验证一个候选值是否可行”这种机械且可控的操作。你不需要洞察所有细节，只要抓住单调性，写出一个正确的check，剩下的事情就交给二分去迭代。这种“猜答案”的思维方式，往往比暴力搜索高效几个数量级，也让人真正体会到算法设计的乐趣。

如果你刚接触这种思想，建议亲手实现一遍切木头问题，再挑战一下假币问题。当你亲手把check函数写出来、看着二分一步步逼近答案时，那种“原来答案可以这样猜”的感觉，真的很棒。

---

关于作者

我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。

这些年累计帮助 多名 学生通过编程特长升入自己心仪的目标学校。

如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）