二分答案——把最值问题变成判断题 - CSP-J

二分答案：把最值问题变成判断题

——从“猜答案”到“验证答案”的聪明方法

在CSP-J的算法题里，有一类问题特别让人头疼：题目要求你找出“最大中的最小”或“最小中的最大”。直接算往往找不到规律，但如果我们换个思路——先猜一个答案，然后验证这个答案是否可行，再用二分法不断调整猜的数字，最后就能找到最优解。这就是二分答案的核心思想。

说白了，二分答案就是：把“求最优值”的问题，变成“给定一个值，判断它行不行”的问题。只要判断函数写得好，剩下的交给二分法去逼近答案。

1. 什么是二分答案？—— 生活里的“猜数字”游戏

想象一下：老师让你猜一个1~100之间的数字，你每次猜一个数，老师会告诉你“大了”或“小了”。你每次根据提示缩小范围，最多猜7次就能猜中。二分答案也是这个原理，只不过“猜”的不是数字本身，而是最优答案。

生活例子：
妈妈有一块大巧克力，要分给你和弟弟两个人。你俩都想吃最多，但妈妈要求每块必须是正方形，且边长必须是整数厘米。那么正方形的边长最大能是多少？
直接算很难，但我们可以猜：

先猜边长=5cm，看能不能切成两块。如果切得出来，说明边长还能更大（比如6cm）；
如果切不出来，说明边长要更小（比如4cm）。
这样反复猜，就能找到最大的可行边长。

在程序中，我们就是用check(mid)函数来扮演“老师”的角色，判断当前猜的答案是否可行。

2. 什么时候用二分答案？—— 看单调性

二分答案不是万能的，它有一个重要前提：答案的可行性必须具有单调性。

如果答案越大，条件越容易满足，这叫单调递增（例如：“至少需要多少个路灯” → 路灯越多，照亮范围越小，越难满足 → 其实是单调递减？要小心！实际中我们常把问题转化成“x是否可行”，然后看x增大时，可行性的变化方向）。
通常我们这样判断：假设最优答案是Ans，那么当x < Ans时，x不可行；当x >= Ans时，x可行（或者反过来）。只要可行性随x单调变化，就可以用二分。

典型场景：

“最大值最小”：比如切绳子，每段越长，能切出的段数越少，可行性下降。
“最小值最大”：比如安装路灯，每个路灯照亮距离越大，需要的路灯越少，可行性上升。
考试分数线：老师想划一条分数线，使得通过的人数不少于某个值。分数线越高，通过的人越少，可行性单调递减。

判断单调性的小技巧：
先想一下，当你把答案变大（或变小）时，条件会变容易还是变难？如果变化方向是单调的，就可以用二分。

3. 如何写出check函数？—— 核心是“贪心+验证”

二分答案的灵魂就是check(x)函数，它返回“当答案取x时，能否满足题目要求”。大多数时候，这个判断可以用贪心策略来写：

比如切绳子：从每根绳子上尽量多地切出长度为x的小段，累加总段数，看是否达到k。
比如分巧克力：对每块巧克力，看最多能切出边长x的正方形几个，总和够不够人数。

注意：check函数要尽可能高效，因为二分过程中要调用很多次（一般几十次）。O(n) 的复杂度通常可以接受。

举个新例子：
有n本书，每本书的页数不同，要把这些书分成连续的k组，每组的总页数不能超过x，问x最小能是多少？（即“最大值最小”问题）
check函数：从左到右扫描，尽可能让每组页数接近x，如果当前组加上下一本会超过x，就新开一组。如果最后组数≤k，说明x可行。

bool check(int x, vector<int>& pages, int k) {
    int current_sum = 0;                // 当前组已经累计的页数
    int groups = 1;                     // 至少需要1组
    for (int p : pages) {
        if (p > x) return false;        // 一本书就超过限制了，不可能
        if (current_sum + p <= x) {
            current_sum += p;           // 加到当前组
        } else {
            groups++;                   // 新开一组
            current_sum = p;
        }
    }
    return groups <= k;                 // 组数不超过k则可行
}

4. 二分答案的两种写法：整数 vs 浮点数

根据答案的类型，二分有两种常见的做法：

(1) 整数二分（答案都是整数）

例如：分巧克力边长、切绳子段数（但绳子长度可以是小数？通常题目会说整数或实数）。
整数二分要注意边界和循环退出条件。常见模板：

int left = 0, right = INF; // 左边界是最小可能，右边界是最大可能
while (left < right) {
    int mid = (left + right + 1) / 2; // 右中位数，避免死循环
    if (check(mid)) {
        left = mid;      // 答案可能更大
    } else {
        right = mid - 1; // 答案必须更小
    }
}
// 最后 left 就是最优答案

或者用另一种风格：

while (left <= right) {
    int mid = (left + right) / 2;
    if (check(mid)) {
        ans = mid;
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

(2) 浮点数二分（答案可以是小数）

例：绳子切成小数长度的段。这时不能直接用while(left < right)，因为浮点数精度问题。
常用做法：固定迭代次数（比如100次），确保精度足够。也可以设定right - left > 1e-6，但迭代次数更保险。

原代码中已经展示了固定100次的方法，对于CSP-J完全够用。

5. 常见错误（新手易踩的坑）

边界设置错误：左边界初始值太小，右边界太大，导致二分找不到正确范围。比如绳子长度，右边界必须大于最长的绳子，否则会漏掉答案。
单调性判断反了：写check时，要确认“x越大越容易满足”还是“x越小越容易满足”。如果弄反，二分方向就错了。
check函数写得不对：比如切绳子时，用(int)(r / len)直接取整没问题，但要注意浮点数除法后取整可能丢失精度（例如1.0/3.0得0.333，取整得0），这恰恰是想要的效果。但千万不要用floor或ceil搞混。
整数二分死循环：在while (left < right)中，如果mid = (left + right) / 2（下取整），且check(mid)为真时执行left = mid，可能导致left一直不变（比如left=0, right=1，mid=0，check(0)为真，left还是0）。解决方法：用mid = (left + right + 1) / 2。
浮点数精度不够：如果题目要求输出保留若干位小数，用固定迭代次数（如100次）通常足够，比直接判断right-left > 1e-8更稳定。

6. 完整可运行示例——整数二分：分巧克力

除了原来的浮点数切绳子，我们再给一个整数二分的经典题（NOIP/蓝桥杯常见）：

题目：有n块巧克力，每块是长方形，长宽已知。要切出k块大小相同的正方形巧克力（边长是整数），问正方形边长最大能是多少？
思路：二分边长，check函数计算每块巧克力能切出多少块边长为x的正方形。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 判断边长为len时，能否切出至少k块正方形
bool check(vector<pair<int,int>>& choco, int len, int k) {
    int cnt = 0;
    for (auto& p : choco) {
        int h = p.first;    // 巧克力高度
        int w = p.second;   // 巧克力宽度
        cnt += (h / len) * (w / len); // 每块可切出的个数
        if (cnt >= k) return true;
    }
    return cnt >= k;
}

int main() {
    vector<pair<int,int>> chocolates = {{10, 8}, {6, 12}, {9, 5}}; // 三块巧克力
    int k = 5;              // 需要5块正方形
    int left = 1, right = 12; // 边长范围：1~最大边长
    int ans = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (check(chocolates, mid, k)) {
            ans = mid;      // 记录可行答案
            left = mid + 1; // 尝试更大的边长
        } else {
            right = mid - 1; // 边长必须减小
        }
    }
    cout << "最大正方形边长: " << ans << endl; // 输出9? 实际验证: 10x8可切1块9x9? 不行，需要调整数据
    // 这里数据仅为示例，实际运行时请根据题目修改
    return 0;
}

注意：示例中的巧克力数据不一定能切出5块边长9的正方形，实际使用时请根据题目测试。

7. 相关指引

二分答案常与以下知识点结合：

二分查找（Bisection Search）：本质相同，只是二分查找直接找值，二分答案套一层判断。
贪心算法：很多check函数用贪心实现，如能切多少段、能分多少组。
最大化最小值 / 最小化最大值：经典问题的标志性词语，遇到这类描述优先考虑二分答案。
CSP-J 常见算法：二分答案经常出现在普及组第二题或第三题，建议多练习“切绳子”“分巧克力”“跳石头”等题目。

掌握了二分答案，你会发现很多棘手的最值问题，其实只需要一个巧妙的猜答案+验证，就能轻松解决。

例题精讲