浅谈二分—— by hyl天梦

时间:2024-01-26 10:22:59

二分

解决范围

二分法可以用来解决这一系列具有单调性质的题,例如求单调函数的零点
其实在小学奥数中就用到了二分法
例如手动开根号,再比如猜数游戏
二分的具体过程就是先取一个中间值,判定一下正确答案在哪边,然后接着再二分,直到找到答案为止
二分法的本质是把求解问题转化成判定问题

优势

二分相对于暴力枚举来讲,判定次数会显著变少
具体来说,如果暴力枚举期望是O(N)次
那么二分只需要O(logN)次就可以得出答案

模板

//整数版
while(l<r)
{
    mid=(l+r)/2;
    if(check(mid)) r=mid;
    else l=mid+1;
}

while(l<r)
{
    mid=(l+r+1)/2;//注意+1
    if(check(mid)) l=mid;
    else r=mid-1;
}
//小数版

while(r-l>eps)
{
    mid=(l+r)/2;
    if(check(mid)>0) l=mid;
    else r=mid-eps;
}
//其中eps=1e-6或1e-8;依照题而定

例题

题目1

我的生日要到了!根据习俗,我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对,每个人会拿到一块派(必须一个派的一块,不能由几个派的小块拼成;可以是一整个派)。
我的朋友们都特别小气,如果有人拿到更大的一块,就会开始抱怨。因此所有人拿到的派是同样大小的(但不需要是同样形状的),虽然这样有些派会被浪费,但总比搞砸整个派对好。当然,我也要给自己留一块,而这一块也要和其他人的同样大小。
请问我们每个人拿到的派最大是多少?每个派都是一个高为1,半径不等的圆柱体。

代码1
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<vector>
#define N 100010
#define ll long long
#define dd double
using namespace std;

int n,f;
dd a[N];
const dd pie=3.1415926535;

bool check(dd mid)
{
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        sum+=a[i]/mid;
    }
    if(sum>=f) return 1;
    else return 0;
}

int main()
{
    cin>>n>>f;
    dd l=0,r=0;
    for(int i=1;i<=n;i++)
    {
        dd x;
        cin>>x;
        a[i]=x*x*pie*1;
        r=max(a[i],r);
    }
    dd eps=0.001;
    while(r-l>eps)
    {
        dd mid=(l+r)/2.0;
        if(check(mid)) l=mid;
        else r=mid-eps;
    }
    printf("%0.3lf",l);
    return 0;
}
题目2

把一个包含n个正整数的序列划分为m个连续的子序列(每个正整数恰好属于一个序列)。设第i个序列的各数之和为S(i),你的任务是让所有S(i)的最大值尽量小。
例如序列1 2 3 2 5 4划分成3个序列的最优方案为1 2 3|2 5 |4,其中S(1)、S(2)、S(3)分别为6、7、4,最大值为7;如果划分成1 2|3 2|5 4,则最大值为9,不如刚才的好。
n<=10^6,所有数之和不超过10^9。

代码2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<vector>
#define N 100010
#define ll long long
using namespace std;

ll n,k,a[N];

bool check(ll mid)
{
    int sum=0,j=1;
    for(int i=1;i<=n;i++)
    {
        sum+=a[i];
        if(a[i]>mid) return 0;
        if(sum>mid)
        {
            j++;
            sum=a[i];
        }
    }
    if(j>k) return 0;
    else return 1;
}

int main()
{
    scanf("%d%d",&n,&k);
    ll l,r=0;
    l=-100;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        l=max(l,a[i]);
        r+=a[i];
    } 
    while(l<r)
    {
        ll mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}
题目3

公园里有n个水塘,需要把这n个水塘中的水排干,水塘中的水在自然条件下1个单位的时间可以蒸发A升水。现在买了1台抽水机,使用抽水机可以让你用1个单位的时间使每个水塘除开自然蒸发的A升水外,还可抽B升水,但在1个单位的时间内只能对1个水塘使用。
要你求出排干所有水塘的最少时间(水塘中的水为0时为排干)。

代码3
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<vector>
#define N 100010
#define ll long long
using namespace std;

ll n,a[N],A,B;

bool check(ll mid)
{
    int sum=0;
    int jian=mid*A;
    for(int i=1;i<=n;i++)
    {
        int ai=a[i]-jian;
        if(ai>0)
        {
            sum+=ai/B;
            if(ai%B!=0) sum++;
        }
    }
    if(sum>mid) return 0;
    else return 1;
} 

int main()
{
    cin>>n>>A>>B;
    ll l=0,r=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        r+=a[i];
    }
    while(l<r)
    {
        ll mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}
/*
5 3 4
19 12 15 23 7
答案:5
*/ 
题目4

给出两个长度为n的正整数有序数组A和B, 在A和B中各任取一个, 可以得到n×n个积. 求第n小的元素。
n<=100000

思路4

判定有多少乘积小于这个答案就可以继续二分

但是怎么判定呢?
由于两个数组都是有序的,所以A数组中可行的乘积对应B数组一定是从头开始的一段序列,并且范围逐渐变小

这样我们O(N)扫一遍,用一个指针维护一下B数组合法位置就可以了

代码4
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<vector>
#define N 100010
#define ll long long
#define dd double
using namespace std;

ll n/*,m*/,a[N],b[N];

bool check(ll mid)
{
    int sum=0,j=1,i=n;
    while(i>=1&&j<=n)
    {
        if(a[i]*b[j]<mid)
        {
            sum+=i;
            j++;
        }
        else i--;
    }
    //cout<<sum+1<<endl;
    sum++;
    if(sum<=n) return 1;
    else return 0;
}

int main()
{
    cin>>n;
    ll l=0,r=0;
    ll max1;
    for(int i=1;i<=n;i++) cin>>a[i],r=max(r,a[i]);
    for(int i=1;i<=n;i++) cin>>b[i],max1=max(max1,b[i]);
    r=max1*r;
    //cin>>m;check(m);
    while(l<r)
    {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}

/*
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<vector>
#define N 100010
#define ll long long
#define dd double
using namespace std;
ll n,a[N],b[N],c[N],tail;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        c[++tail]=a[i]*b[j];
    sort(c+1,c+tail+1);
    cout<<c[n];
}
*/

/*
5
12 23 112 231 345
23 123 423 2390 8492
答案:2829
5
1 2 3 4 5
2 3 4 5 6
答案:5 
*/
题目5

一年一度的“跳石头”比赛又要开始了!
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。
为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)。
求最短跳跃距离的最大值
N,M<=50000

代码5
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<deque>
#define dd double
#define ll long long
#define N 10000100
using namespace std;
ll n,m,a[N];
ll l;

bool check(ll mid)
{
    int now=0;
    int sum=0;
    for(int i=1;i<=n+1;i++)
    {
        if(a[i]-a[now]<mid) sum++;
        else now=i;
    }
    //cout<<mid<<" "<<sum<<endl;
    if(sum<=m) return 1;
    else return 0;
}

int main()
{
    cin>>l>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    a[n+1]=l;
    ll r=l;
    l=0;
    while(l<r)
    {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
} 

三分

与二分法类似,三分法可以用来解决具有单峰性质的题
三分的具体过程就是先取两个中间值,分别位于1/3和2/3处,根据单峰性判定一下正确答案在前2/3还是后2/3,然后接着再三分,直到找到答案或答案的近似值为止
二分法每次把答案范围缩小一半,三分法每次把答案范围变为原来的2/3,他们的时间复杂度都是O(log(n))的

题目1

在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。小y在AB上的移动速度为P,在CD上的移动速度为Q,在平面上的移动速度R。现在小y想从A点走到D点,他想知道最少需要走多长时间?

思路1

小y走的路径一定是三条线段组成的折线
如果把离开AB线段的点设为x,到达CD的点设为y,总时间设为z,那么z是关于x,y的二元函数
可以证明这个函数形如一个山丘,也就是说可以先三分x再三分y求出z的最值

代码1

详见https://www.cnblogs.com/TianMeng-hyl/p/12309214.html