二分答案类问题的基本应用

一.知识介绍

二分是一种十分优秀的思想，他可以帮助我们每次把问题规模减半，直到找到正确答案位置，在很多时候，他可以帮我们节约很多时间，在说二分答案之前先简单介绍一下二分查找问题，这是一个非常基本的二分问题，如果你要找这个序列中的一个数，那么先将他排序，然后设置起点为left终点为right，每一次循环先算出mid如果mid小于目标则将left移动至mid+1如果mid大于等于目标则让right=mid，对于这个问题我们一定要注意小于情况的时候要移动至mid+1，否则如果left和right相邻，right位置是正解，但由于mid自动向下取整而导致循环不会结束。需要注意的是二分查找可以选择l==r为边界条件，也可以选择自己设置循环次数来限制，因为算法的规模是以二的幂次增加的，只需设置循环60次，就可以保证2的六十次方以内的数据可以被找到。
下面是一段简单的二分查找代码

int target;
while(l!=r)
{
mid=(l+r)/2;
if(target<=mid)r=mid;
else l=mid+1;
}

说完了二分查找，那么我们继续看二分答案问题，事实上，二分答案只是一种抽象化模型，它的意义是在一段整数区间里，每个数可能满足条件或不满足条件，且符合单调性（先是连续一段不满足后面都是满足）我们可以通过二分找到第一个满足条件的数，在计算机中满足条件与否可以用true和false或1和0来表示，该模型的抽象模型就是找到第一个满足一的值，也就是说在一段形如 0000 11111 的单调序列中找到第一个一，不过不一样的是我们只需判断对错也就是mid是不是1，在这里我们需要注意如果mid是0那么第一个以一定在它的右边，所以我们去l=mid+1，而mid为1则包括了他是第一个1和前面有一的可能性，所以我们要保留r=mid这个边界需要根据实际情况进行调整。
实际上二分查找也可以用这个模型来处理，我们把问题转化成找到大于等于目标的最小数，也就是如果答案大于等于目标就是1否则为0，就转化成了二分答案问题
应该来说对于大于等于目标的最小数或小于某数的最大数，都是我们要注意的关键词，如果题目蕴含这样的意义，那么通常这道题就可以用二分来解决
实际上我们依然要处理一些特殊的边界情况才能保证二分答案的准确性，其实就是如果整个序列都为0或1，我们需要在起点之前和终点之后赋值保证循环可以正常结束，处理好边界问题，二分答案的模型也应该讲完了。
但是对于这一模型，刚开始我们很难直接应用他解决问题，因为很多二分的题都会很隐蔽，需要我们自己寻找问题的转换方法。下面就简单看几道例题

实际应用

1.
这道题题意很好理解就是有一个目标数值，我们要在尽可能少砍树的前提下满足条件，所以我们要找到最合适的位置来砍树，这道题的二分判断条件其实很明显，就是在这个位置砍树够不够满足条件，我们先找到最高的一颗数，然后开始二分，只需借助一个判断函数就可以找到正确答案
代码如下

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[10000004],tmp,l,r,ans，mid;
bool check(long long x){
    for(long long i=1;i<=n;i++)
        if(x<a[i])tmp+=a[i]-x;
    return m<=tmp;//骚写法，如果满足条件则返回1 
}
int main(){
    cin>>n>>m;
    for(long long i=1;i<=n;i++)cin>>a[i],r=r>a[i]?r:a[i];//h找到最大值
    while(l<=r){
         mid=(l+r)>>1;tmp=0;
        if(check(mid))l=(ans=mid)+1; 
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}

这道题表示的比较明显，下面看一个更复杂一点的问题。

我们要割绳子，目标分成k段，每个绳子可以分成有限个k段，问每段所能达到的最长，首先这道题只保留小数点后两位，为了避免浮点误差，我们先将所有数据乘100，最后在除100就可以解决这个问题，下面我们来找一下这道题的二分判断条件，比刚刚稍微复杂一点，其实问题就是如果每段这么长能否分成k或k以上的段落
代码也很简单，就注意一下每段绳子/当前要求段长就是他能分成的段数，和上面一样(这段代码没有乘100在除100，但实际上这样可能会引起一些浮点误差）

#include<bits/stdc++.h>
using namespace std;
int n,k;
double a[10005],l,r,mid;
char s[100];
inline bool check(double x)
{
    int tot=0;
    for(int i=1;i<=n;i++)tot+=floor(a[i]/x);
    return tot>=k;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%lf",&a[i]),r+=a[i];
    while(r-l>1e-4)
    {
        mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%.2lf",l); 
    return 0;

其实上面两道题都属于最明显的二分问题，这个博客也只记录我自己初学二分时遇到的一些简单二分问题，下面最后看一个和贪心结合的二分问题
先看题目

我第一次看这个题，很难想象他可以用二分去解决，我没有找到合适的判断条件，知道我看到这个题

这个应该是他的简化模型，很容易看出来是一个贪心问题，能去就取，不能去就分段，于是我想到了上面题的判断条件，应该是当每段为x时能不能满足段数小于M也就是在111111 00000的序列中找到最后一个1，我们只需修改一些mid’的赋值和边界情况问题就迎刃而解了

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],l,r,mid,ans;
inline bool check(int x)
{
    int tot=0,num=0;
    for(int i=1;i<=n;i++)
    {
        if(tot+a[i]<=x)tot+=a[i];
        else tot=a[i],num++;
    }
    return num>=m;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),l=max(l,a[i]),r+=a[i];
    while(l<=r)
    {
        mid=l+r>>1;
        if(check(mid))l=mid+1;
        else r=mid-1;
    }
    cout<<l;
    return 0;
}

做了这几道二分类的问题，我意识到二分其实有很强的泛用性，有很多问题都可以转化为二分问题去解决，这些只是最基础的二分，因为在判断条件处题目可以出的更隐蔽，并且结合更多其他知识点来解决，所以我们要多积累经验，遇到大于等于目标的最小数或小于某数的最大数要与二分多联想。