二分学习笔记

写在前面：本文中的“单调”不包括“单调不变”。（我不说你们应该也不会想到）

一、算法引入

如果我们要用一个数列(各个位置要有相应的数字形式的下标，且我们的这个下标可为小数）的某一个子序列来求一个值，那么当这个子序列的值是单调的，那么显然为了让我们整个过程的平均复杂度低一些，我们可以考虑使用这样或类似的算法：设\(l\),\(r\)分别代表现在搜索到的区间的左端点和右端点的位置，设一阈值\(x\),当位置\(x\)到区间[\(l\),\(x\)]包含我们要的答案时，l不变，r=x；否则r不变，l=x+y(y是一个非负数，具体的值自己定），r不变。（显然，阈值x取\(\lfloor\)(\(l\)+\(r\))/2\(\rfloor\)最好）

这样的算法大概就是二分算法了。

Tips:二分算法包括二分查找、二分答案、整体二分等算法。
这里我要先说一下，二分法刚学时你可能会感觉它很难，但只要你多模拟二分的过程，肯下功夫，你也会慢慢领悟到其中的奥妙了。（然后你也许就可以秒切各种二分可以做的很水的部分分，甚至直接用二分秒切很多题了(doge)）

二、算法应用

2.1 二分查找

指在一个数列中用二分法来查找某个值。
例题一 Luogu P2249查找
\(Code\)&\(Explanation\)

#include<bits/stdc++.h>
using namespace std;
int a[1000005],m,q,n;
int find(int x){
    int l=1,r=n,mid;
    while(l<r){
        mid=l+r>>1;//下面五行为基本判断+端点修改
        if(a[mid]>=x){
        	r=mid;
        }
        else{
        	l=mid+1;
        }
    }
    if(a[r]==x){
    	return r；
    }
    else{
    	return -1;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>q;
        cout<<find(q)<<" ";
    }
    return 0;
}

2.2 二分答案

顾名思义，大概就是对某一个问题的答案进行二分，以求出一个最优解
例题一 Luogu P1873 EKO/砍树

\(Code\)&\(Explanation\)

//本题要我们求最大的一个可以得到至少M米木材的H
//我们可以发现，H值变大程中砍下木材的长度是单调不增的，那么我们就可以进行相关的二分答案了（以H为键值）
#include<bits/stdc++.h>
using namespace std;
long long a[2000000],m,n;
bool p(int h){
    long long ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]>h){
            ans+=(a[i]-h);
        }
    }
    return ans>=m;
}
int main(){
    long long l=0,r=1e9,g,mid;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }//下面的一段while循环为本题二分答案的主体部分
    while(l<=r){
        mid=l+(r-l)/2;
        if(p(mid)){//判断
        	g=mid;l=mid+1;//g是用来记录答案的
        }
        else{
        	r=mid-1;
        }
    }
    printf("%lld",g);
    return 0;
}

例题二 Luogu P1542 包裹快递
大体的算法与上一题的差不多，但要注意精度（lmid是用来防止死循环的）
\(Code\)&\(Explanation\)

//二分
//要用long double
#include<bits/stdc++.h>
#define F(i,j,k) for(int i=j;i<=k;++i)
#define ldb long double
using namespace std;
ldb l=0.0,r=10000000.0,ans=1.0*INT_MAX,ll=-1,rr=1;
int n;
struct node{
    int x,y,s;
}pos[200005];
int read(){
    int w=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+c-'0';
        c=getchar();
    }
    return w;
}
ldb mmax(ldb aa,ldb bb){
    if(aa>=bb)
        return aa;
    return bb;
}
ldb mmin(ldb aa,ldb bb){
    if(aa<=bb)
        return aa;
    return bb;
}
int main(){
    n=read();
    F(i,1,n){
        pos[i].x=read();pos[i].y=read();pos[i].s=read();
    }ldb mid=l+r/2.00;
    while(l<=r){//ll=l,rr=r;
        bool ok=true;
        ldb mid=(l+r)/2.0;
        ldb tim=0.00;
        for(int i=1;i<=n;++i){
            ldb tt=1.00*pos[i].s/mid+1.00*tim;
            if(tt>1.00*pos[i].y){
                ok=false;
                break;
            }
            else{
                tim=mmax(tt,1.00*pos[i].x);
            }
        }
        if(ok&&mid<=lmid){
            r=1.0*mid-0.0001;
            ans=mmin(ans,mid);
        }
        else{
            l=1.0*mid+0.0001;
        }
    }
    printf("%.2Lf",ans);
    return 0;
}

2.3 整体二分

to be continued;

三、习题

3.1 Luogu P1102 A-B数对
to be continued;

本文如有什么大问题，请私信告知我或在本篇博客下评论告知我。