二分答案

ynokis · 2023-01-17 22:53:47 · 个人记录

首先理解什么是“二分答案”：

答案，即枚举答案，是一种解题方法，主要作用是化求解为判定，降低难度。如果：给出一个解，判定这个解是否合法（注意：只需要判定是否合法）十分简单可行，那么该题目便可以使用答案。

二分，是对问题状态空间的一种遍历方式，主要作用是降低时间复杂度。二分建立在答案的基础上。如果存在一个分界点 p ，使问题区间划分为 [l,p) 和 [p, r] 两部分，并且一部分有解，一部分无解，那么就可以以二分的方式进行枚举。也就是说，二分成立的关键是能找到无数个这样的划分点。

答案部分对应代码中的 bool check(mid) 函数，需要根据题目条件判断 mid 值是否合法。

二分部分对应代码中的二分部分，一般分为两类：

第一类：

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}

第二类：

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

判断使用哪一类的标准一般是答案所在的区间。一般而言（做题少待hack）：求最小值使用左区间，即第一类；求最大值用右区间，即第二类。

以最小值为例：当 mid 成立时，要寻找有没有更小的答案，自然要将 mid 设置为右界，往左去找。