倍增二分及与其它算法的结合

He_hyz · 2023-08-16 14:23:44 · 个人记录

倍增二分

前言

现在最流行的二分算法是利用分治的思想，今天给大家介绍一种倍增思想的二分方法：倍增二分。其实已经有一些人想出了倍增二分并在使用，这里只是给大家做一总结。为了避免混淆，我们称之前的二分方式为朴素二分，新的二分方式为倍增二分。

思想

顾名思义，倍增二分其实和分治没有太大关系，主要是倍增的思想。因为任何一个十进制整数都能表示为二进制的形式，换言之，通过枚举二进制位和限制条件组成十进制整数，推出最后的答案。

过程

枚举每一个二进制位 i=2^x(x\in \mathbb N)，满足条件的就更新答案，不满足就跳过。然而枚举的顺序一定要从大到小，因为如果此位不满足条件，即使后面的所有位都满足对答案的影响也不会超过这一位对答案的影响，这样每一步的对答案产生的影响都是绝对的，是其它后面的位无论如何都无法代替的。但是如果从小到大枚举，程序会把满足条件的位一直更新答案，有可能此位还没有查找到答案，下一位就跳过了答案很多。

如图，一般的单调关系可以表示为图①和图②的升序和降序。1 表示第一个等于 x 的位置，如果我们要查找位置 1，那么就是将 i < x 的加进答案。2 表示最后一个等于 x 的位置，如果我们要查找位置 2，那么就是将 i \leq x 的加进答案。图②中的降序同理。然而我们观察如果要查找位置 1 和位置 3，只把小于 x 或大于 x 的加 i 进答案显然是到达不了最终的地方的，只会停留在它们的前一个位置。但是我们要查找的是最终的位置 1 或 3，所以应在最后给答案加一。请读者理解后自己想一想在两个单调序列中如何求大于 x 的第一个位置。

举例

当然文字描述是十分抽象的，接下来举一个倍增二分查找的例子来说明。二分查找大家都知道，就是在一个单调的序列里查找一个数的位置。比如说我们要在数轴上找一个位置 13。按照步骤，我们会先试探到 16。比 13 大，不满足条件，跳过。接下来我们会试探到 8，比 13 小，加进答案。此时答案为 8，接着会试探 4、2、1，因为试探到 4、1 时满足条件，所以最终会到达到目标值为：8+4+1=13。

时间复杂度及算法正确性证明

因为两种算法中的模拟部分，也就是 check 函数是一样的，所以我们只讨论在二分过程中两种算法不同的时间复杂度。

朴素二分：设 n 为序列长度。每次把区间从中间分成两半去找符合条件的那一个区间，相当于是把整个区间分成了一棵完全二叉树，深度最多有 \lceil\log_2 n \rceil 层，及最多能分 \lceil\log_2 n \rceil 次，时间复杂度为 O(\log n) 。

倍增二分：设 n 为序列长度。我们要保证初始能完全覆盖整个区间，即 i=2^x \geq n，初始值 x=\lceil \log_2 n \rceil，那么 ans= \sum_{x=\lceil \log_2 n \rceil}^0q\times 2^x，其中 q \in \{0,1\}，ans 可以覆盖到区间 [1,n] 中的每一个数，即可以试探到区间 [1,n] 的每一个位置，时间复杂度为 O(\log n) 。（参考资料）

好处

既然倍增二分和朴素二分的复杂度是一样的，那么我们为什么要去使用它呢？我想原因大概有以下两点：

代码量较少于朴素二分，只需要一个 for 循环枚举 i，再加一个 if 判断是否满足条件即可。
朴素二分解决有些问题时边界问题较为复杂，倍增二分则不用考虑朴素二分的边界问题。

倍增二分解决其它二分问题

实数域上的二分

实质上实数域上的二分和整数域上的二分十分相似，区别是实数是具有精度的，显然只枚举整数部分是达不到对精度的要求的，所以只需要让试探的长度 i(i \in \mathbb Z) 和 ans 变为浮点型，控制一个严格小于答案精度的 eps，保证在这个精度内每一处位置都能试探到，一般的取值为 i\geq 10^{-7}。

三分

我们发现函数值的增长率和 x 值存在着单调关系：如果函数波峰向上，函数值增长率会随着 x 增长而减小。那么便可以二分 x 值，控制它的增长量，因为是实数域，应按实数域上的二分处理。

倍增三分的鲁棒性

在实数域上的倍增三分可能会因为精度，比如说控制精度过大或过小而出现一些问题。虽然可能在练习时没有考虑那么多，代码有一些漏洞，但测试数据有限，常常也会 AC。可是为了面对比赛中的强大数据，建议养成好习惯：使用倍增三分法时，在推出最终的答案后和答案周围几个点再比对一下，可能会有更优的情况。

应用

这是一些涉及到二分题目的注意事项：

如果此题没有单调性，可以在允许的情况下先排序再二分。
要善用 lower_bound 和 upper_bound，如果只有二分查找可以运用，节省代码量。
模拟中要善用其他算法，和前缀和、差分等算法结合，更能体现二分的便利。
如果查找的是数组的下标，一定要判断不能越界，当心 RE。

例题

二分查找模板

P2249 【深基13.例1】查找

#include<bits/stdc++.h>
using namespace std;
int n,m,arr[1000005]; 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    while(m--)
    {
        int x,ans=0;
        cin>>x;
        for(int i=1<<30;i;i/=2)
            if(ans+i<=n&&arr[ans+i]<x)
                ans+=i;
        if(arr[++ans]!=x)
            cout<<"-1 ";
        else 
            cout<<ans<<" ";
    }
    return 0;
}

二分答案模板

倍增二分答案实现时尽量要画出两个变量的单调关系，这样会比较直观，有助于分析解题。下面借此模板题给大家讲述一般倍增二分答案的做法。

P1824 进击的奶牛

如图我们发现牛的数量越少，相邻两头牛的最近距离就越大。而牛的数量题目已经给出，是 C 头，我们要求的是相邻两头牛的最近距离的最大值，便是图中竖线的位置。那么将大于等于 C 的 i 加入答案即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int arr[N],n,c;
bool check(int x)
{
    int cnt=1,sum=arr[1];
    for(int i=2;i<=n;i++)
        if(arr[i]-sum>=x)
        {
            cnt++;
            sum=arr[i];
        }
    return cnt>=c;
}
int main()
{
    cin>>n>>c;
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    sort(arr+1,arr+n+1);
    int ans=0;
    for(int i=1<<30;i;i/=2)
        if(check(i+ans))
            ans+=i;
    cout<<ans;
    return 0;
}

三分模板

P3382 【模板】三分法

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-10;
int n;
double l,r,a[15],ans;
double f(double x)
{
    double sum=0;
    for(int i=n;i>=0;i--)
        sum+=a[i]*pow(x,i);
    return sum;
}
int main()
{
    cin>>n>>l>>r;
    for(int i=n;i>=0;i--)
        cin>>a[i];
    double ans=l;
    for(double i=r+1;i>=eps;i/=2)
    {
        double m1=ans+i,m2=ans+i+eps;
        if(m1<=r&&f(m1)<f(m2))ans+=i;
    }

    printf("%0.5lf",ans);       
    return 0;
}

三分的鲁棒性

[ABC279D] Freefall

#include<bits/stdc++.h>
using namespace std;
#define int long long
const long double eps=1e-7;
int a,b,ans=-1;
long double check(long double g) 
{
    if(!g)return 1e18;
    return b*1.l*(g-1)+a*1.l/sqrt(g);
}
signed main() 
{
    cin>>a>>b;
    for(long long i=2e18;i;i/=2)
        if(check(ans+i+1)>check(ans+i+2)||fabs(check(ans+i+1)-check(ans+i+2))<eps) 
            ans+=i;
    long double pr=check(ans+2);
    if(ans+1>=1)pr=min(pr,check(ans+1));  
    pr=min(pr,check(ans+3));
    printf("%0.6Lf",pr);
    return 0; 
}

倍增二分与其它算法的结合

倍增二分与差分的结合

P1083 [NOIP2012 提高组] 借教室

简洁题意

有一段长度为 n 的序列，共有 m 次区间修改，每次修改是给区间 [s_i,t_i] 中的所有数减 d_i，求第几次修改后序列中出现了负数，如果最终也没有出现负数则输出 -1。

思路

看到题目发现租借教室的人数和教室数量存在单调关系，显然租借的人数越多，教室数量越少。那么便二分租借的人数，将不够租借的情况加入答案，最后答案加一。

处理细节

模拟中有 m 个需要修改的区间，一个一个修改的时间复杂度为 O(mn)，而 m,n\leq 10^6，显然时间上是不允许的。因为是区间修改，单点查询，所以在这里我们可以用上差分的技巧，先定义一个差分数组 c，在s[i] 的位置上增加 d[i]，在 t[i]-1 的位置上减少 d[i]。这样就完成了区间修改。然后遍历一遍区间 [1,n] 第 i 位改变的教室数量为 \sum_{j=1}^i c[j]，既然是顺序遍历，我们可以用 l 记录差分数组的前缀和，即得到了修改后的原数组。模拟部分整体的时间复杂度优化到了 O(m+n)。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,m,r[N],d[N],s[N],t[N],ans,c[N],l;
bool check(int day)
{
    l=0;
    memset(c,0,sizeof(c));
    for(int i=1;i<=day;i++)
    {
        c[s[i]]+=d[i];
        c[t[i]+1]-=d[i];
    }
    for(int i=1;i<=n;i++)
    {
        l+=c[i];
        if(l>r[i])return false;
    }
    return true;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>r[i];
    for(int i=1;i<=m;i++)
        cin>>d[i]>>s[i]>>t[i];  
    if(check(m))
    {
        cout<<"0";
        return 0;
    }
    for(int i=(1<<30);i;i/=2)
        if(ans+i<=1e6&&check(ans+i))ans+=i;
    cout<<"-1"<<endl<<ans+1;
    return 0;
}

倍增二分与前缀和的结合

P1314 [NOIP2011 提高组] 聪明的质监员

简洁题意

给定 n 个矿石，每个矿石有两种属性 w 和 v，又给定 m 个区间，最终通过控制参数 W 的值，按照以下公式计算得出对应的 y ，求 y 和题目中给定的 s 的相差最小值。

y=\sum_{i=1}^m(\sum_{j=l_i}^{r_i}[w_j\geq W]\times \sum_{j=l_i}^{r_i}[w_j\geq W] v_j)

思路

看到题目发现参数 W 和矿石检验结果 y 存在单调关系，显然 W 越大，y 越小。那么便二分 W，因为要求一个绝对值，我们便记录一个小于 s 的 y 和一个小于等于 s 的 y，看哪个更接近 s，就是最终的答案。

处理细节

和刚那题很像，也是要在每次模拟时遍历每一个区间，记录答案，时间复杂度为 O(nm)，而 n,m\leq 2 \times 10^5，显然时间是不允许的。因为是单点修改，区间查询，所以在这里我们可以用上前缀和的技巧，先定义两个前缀和数组 sum1,sum2 一个储存满足条件的物品个数的前缀和，另一个储存满足条件的物品价值的前缀和，这样就完成了单点修改。访问时 y=\sum_{i=1}^m(sum1[r[i]]-sum1[l[i]-1])\times(sum2[r[i]]-sum2[l[i]-1])。模拟部分整体的时间复杂度优化到了 O(n+m)。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,m,s,y,ans1,ans2;
int w[N],v[N],l[N],r[N],sum1[N],sum2[N];
int check(int W)
{
    memset(sum1,0,sizeof(sum1));
    memset(sum2,0,sizeof(sum2));
    y=0;
    for(int i=1;i<=n;i++)
    {
        if(w[i]>=W)
        {
            sum1[i]+=v[i];
            sum2[i]++;
        }
        sum1[i]+=sum1[i-1];
        sum2[i]+=sum2[i-1];
    }
    for(int i=1;i<=m;i++)
        y+=(sum1[r[i]]-sum1[l[i]-1])*(sum2[r[i]]-sum2[l[i]-1]);
    return y;
}
signed main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i];
    for(int i=1;i<=m;i++)
        cin>>l[i]>>r[i];
    for(int i=(1ll<<50);i;i/=2)
    {
        if(check(ans1+i)>=s)ans1+=i;
        if(check(ans2+i)>s)ans2+=i;
    }
    ans1=abs(check(ans1+1)-s);
    ans2=abs(check(ans2)-s);
    cout<<min(ans1,ans2);
    return 0;
}

倍增二分与搜索的结合

P2658 汽车拉力比赛

简洁题意

给定一个 n\times m 的二维平面，平面上每个点都有一个值，又在这个平面上给定一些点，求在包含所有给定点的连通图中最大的相邻两点数值之差的最小值，一个点与其上、下、左、右的四个点是相邻的。

思路

看到题目发现能到达路标的个数和赛道的难度系数 D 存在单调关系，显然能到达路标的个数越多，难度系数 D 越大。于是可以二分难度系数 D，在 check 函数里跑 BFS，将无法到达所有路标的加进答案，最后答案加一。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,a[N][N],ans=-1,cnt,x,y,sum;
bool v[N][N],t[N][N];
int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
struct node
{
    int x,y,now;
};
bool bfs(int d)
{
    memset(v,0,sizeof(v));
    sum=1;
    queue<node>q;
    q.push((node){x,y,1});
    v[x][y]=1;
    while(!q.empty())
    {
        node s=q.front();q.pop();
        if(sum==cnt)return false;
        for(int i=0;i<4;i++)
        {
            int xx=dx[i]+s.x,yy=dy[i]+s.y;
            if(xx<1||xx>n||yy<1||yy>m)continue;
            if(v[xx][yy]||abs(a[s.x][s.y]-a[xx][yy])>d)continue;
            v[xx][yy]=1;
            if(t[xx][yy])sum++;
            q.push((node){xx,yy});
        }
    }
    return true;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)   
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>t[i][j];
            if(t[i][j])cnt++,x=i,y=j;
        }
    for(int i=(1<<30);i;i/=2)
        if(bfs(ans+i))ans+=i;
    cout<<ans+1;
    return 0;
}

倍增二分与最短路的结合

P1462 通往奥格瑞玛的道路

简洁题意

给定一个有 n 个点、m 条边的无向有权图，每经过一个条边就会损失对应的血量，初始血量为 b，从节点 1 到节点 n 的路径中使血量不为负的情况下求沿途经过的点中点权最大值最小是多少。

思路

这道题和刚刚的那道题很像，其实就是把跑 BFS 换成跑 Dijkstra 或 SPFA，然后二分收取的费用，把每次跑完剩余的血量比 b 大的加进答案，最后答案加一。

AC Code

Dijkstra：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+5;
int n,m,head[N],tot,b,x,y,dd,d[N],a[N],ans;
bool v[N],p=1;
struct node
{
    int next,to,dis;
}edge[10*N];
void add(int from,int to,int dis)
{
    tot++;
    edge[tot].to=to,edge[tot].dis=dis;
    edge[tot].next=head[from];
    head[from]=tot;
}
int check(int cost)
{
    if(cost<a[1]||cost<a[n])return 1e9;
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    priority_queue<pair<int,int> >q;
    q.push(make_pair(0,1));
    d[1]=0;
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if(v[x])continue;
        v[x]=1;
        for(int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,dis=edge[i].dis;
            if(a[y]<=cost&&v[y]==0&&d[y]>d[x]+dis)
            {
                d[y]=d[x]+dis;
                q.push(make_pair(-d[y],y));
            }
        }
    }
    return d[n];
}
signed main()
{
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    while(m--)
    {
        cin>>x>>y>>dd;
        add(x,y,dd);
        add(y,x,dd);
    }
    for(int i=(1<<30);i;i/=2)
        if(check(ans+i)>b)ans+=i;
        else p=0;
    if(p)cout<<"AFK";
    else cout<<ans+1;
    return 0;
}

SPFA：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+5;
int n,m,head[N],tot,b,x,y,dd,d[N],a[N],ans;
bool v[N],p=1;
struct node
{
    int next,to,dis;
}edge[10*N];
void add(int from,int to,int dis)
{
    tot++;
    edge[tot].to=to,edge[tot].dis=dis;
    edge[tot].next=head[from];
    head[from]=tot;
}
int check(int cost)
{
    if(cost<a[1]||cost<a[n])return 1e9;
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    queue<int>q;
    q.push(1);
    d[1]=0;
    v[1]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        v[x]=0;
        for(int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,dis=edge[i].dis;
            if(a[y]<=cost&&d[y]>d[x]+dis)
            {
                d[y]=d[x]+dis;
                if(!v[y])q.push(y);
            }
        }
    }
    return d[n];
}
signed main()
{
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    while(m--)
    {
        cin>>x>>y>>dd;
        add(x,y,dd);
        add(y,x,dd);
    }
    for(int i=(1<<30);i;i/=2)
        if(check(ans+i)>b)ans+=i;
        else p=0;
    if(p)cout<<"AFK";
    else cout<<ans+1;
    return 0;
}