二分答案

什么是二分答案？

二分答案是对答案以二分的方式进行枚举，验证每个答案的可行性，最终找出最优解。

二分答案可以干什么？

二分答案适用于有连续的可行解和连续的不可行解拼凑出的答案区间，并且需要求最优解的时候

二分答案的使用条件：

二分答案对于答案的区间有要求：单调、有界，

单调是指把答案空间按照一定的规则排列（常见的是按照大小排序），可行解在一边，不可行解在另一边，可行解和不可行解不能混杂在一起

假如整个序列具有单调性，且一个数x为可行解，那么一般的，所有的x'(x'<x)都是可行解。并且，如果有一个数y是非法解，那么一般的，所有的y'(y'>y)都是非法解。

只有这样，我们才能放心地移动left和right

有界则是从二分继承来的要求，不多解释

二分答案模板：

//ans存储经过验证的答案

//left, right, mid代表左边界，右边界，中间值

while(left<=right)

{

　　mid = (left + right) / 2;

　　if(judge(mid))　　　　//关键代码，检验答案mid是否是可行解,可行true，不可行false

　　　　{

　　　　　　……　　　　//left或right移动

　　　　　　ans = mid;　 //记录可行解

　　　　}

　　else

　　　　……　　　　//left或right移动

}

……//输出ans

洛谷例题：

P2678 跳石头  这是题解以及大佬对二分答案的讲解 ---> https://www.luogu.com.cn/blog/user20197/solution-p2678

P3853 路标设置

P1182 数列分段

P1163 银行贷款

这只是比较简单的二分答案，较难的做了之后会更新

下面是跳石头和数列分段的代码：

//跳石头


#include <stdio.h>

long long n, stone[50002], max_minjump, count, leave_max, length, ans;

void judge(long long mid)
{
    for (long long i = 0; i <= n; i++)
    {
        long long j = i + 1;
        while (stone[j] - stone[i] < mid && j <= n + 1)
        {
            j++;
            count++;
        }
        if (j > n + 1)
            return;
        i = j - 1;
    }
}

int main()
{
    scanf("%lld", &length);
    scanf("%lld", &n);
    scanf("%lld", &leave_max);

    for (long long i = 1; i <= n; i++)
        scanf("%lld", &stone[i]);
    stone[n + 1] = length;

    long long left = 0, right = length, mid = 0;

    while (left <= right)
    {
        count = 0;
        mid = (left + right) / 2;
        //judge
        judge(mid);

        if (count <= leave_max)
        {
            left = mid + 1;
            ans = mid;
        }
        else
            right = mid - 1;

        
    }

    printf("%lld ", ans);
    return 0;
}

//这个题目有点特殊，需要将ans与数组最大值max进行比较，取两者较大值
#include <stdio.h>

long long num[100002],n,m,ans,max;

long long judge(long long mid)
{
    long long sum = 0, count = 1;
    for (long long i = 0; i < n; i++)
    {
        sum += num[i];
        if (sum > mid)
        {
            count++;
            sum = num[i];
        }
    }
    return count;
}

int main()
{
    scanf("%lld", &n);
    scanf("%lld", &m);
    for (long long i = 0; i < n; i++)
    {
        scanf("%lld", &num[i]);
        max=(max>=num[i])?max:num[i];
    }

    long long l = 0, r = 1e9, mid=0;
    while (l <= r)
    {
        
        mid = (l + r) / 2;
        long long count = 0;
        count = judge(mid);
        if (count <= m)
        {
            r = mid - 1;
        }
        else
            l = mid + 1;
        if (count == m)
            ans = mid;
    }
    printf("%lld",(max>ans)?max:ans);
    return 0;
}