二分题目总结

二分作为基础算法,主要有两种题型

二分题目总结

 1.二分查找

二分查找是利用二分搜索时间复杂度O(logn)的性质,对于算法中某一步骤需要优化的时候,使用二分查找优化,又分为实数二分和整数二分

二分题目总结

(1).实数二分 

二分题目总结

实数二分比较简单,主要是在数轴上寻找某一个点,是否满足性质

1.数的三方根

#include <iostream>
#include <algorithm>
using namespace std;
const int N=10000;
int main()
{
    double n;
    cin>>n;
    double l=-10000,r=N;
    while(r-l>1e-7)        //一般都是要多加几位,保持精度
    {
        double mid=(l+r)/2;
        if(mid*mid*mid>=n)
            r=mid;
        else
            l=mid;
    }
    printf("%.6f",r);
}

2.银行贷款

(2)二分优化,二分查找

二分模板

二分优化分为两种

二分题目总结

 1.寻找一个点

寻找一个点就是在区间中寻找唯一满足条件的点(没有重复),主要代表类型有抽签问题

其中四平方和就是经典的抽签问题

2.寻找一段区间

在一个区间中,可能存在多个点满足要求,他们的值相同,我们可以运用二分性质

先找左侧边界,再找右侧边界,就是最后的答案

二分题目总结
 2.二分答案

二分答案是利用二分的性质(寻找第一个满足要求的点,寻找最后一个满足要求的点)

二分答案能够使用的前提是:

1.二分性二分题目总结

在一个点的左边全部满足要求,右边全部不满足要求

反之也成立

2.单调性  满足二分性的时候通常情况下都满足单调性,但是单调性不是必要的前提

二分答案的模板(以第一个满足的点为例)

while(l<r)
{
    int mid=l+r>>1;
    if(check())     //满足某个要求   
        r=mid;
    else
        l=mid+1;
}

check()函数是什么 

check函数表示某种要求,这种要求在一个点的左边全部不满足,在一个点的右边全部不满足

check实质就是验证答案是否可行,可行就返回true,不可行就false

check函数通常控制在O(n)的时间复杂度,对于很多情况,check()函数的实现可以使用不同的优化

二分题目总结

 我们先来介绍一下模拟实现check()

(1)模拟

模拟的实现check():

通常会使用到一些  简单数学  简单递推   

简单数学模拟

机器人跳跃问题

 

P1873 [COCI 2011/2012 #5] EKO / 砍树

P2440 木材加工

(2)贪心优化

直接照着题意来太难实现了?代码太长不会做了?时间复杂度太高卡壳了?

不如试试贪心优化,贪心优化check函数!

贪心优化首先是一个经典问题:分书

分书问题

有N本书排成一行,已知第i本的厚度是Ai

把它们分成连续的M组,使得T最小化,T表示厚度之和最大的一组的厚度

这个问题怎么贪心?

很简单,要放的书要超出给定值了,那么我们就**别放进去了

二分题目总结

bool check(int x)
{//这里的书必须单调递增
//x==t,m是给定的最多组数
    int cnt=0;
    for(int i=0;i<n;i++)
        if(a[i]+b[cnt]>x)
         {
             b[++cnt]=a[i];              
         }
        else
            b[cnt]+=a[i];
return cnt<=m;
}

或者

bool check(int x)
{//一样的,一组高度必须单调递增
    int group=1,rest=size;
    //res表示一个组剩余容量
    for(int i=0;i<n;i++)
    {
        if(res>=a[i])  rest-=a[i];
        else group++,rest=size-a[i];
    }
    return group<=m;
}

P1182 数列分段 Section II

P2678 [NOIP2015 提高组] 跳石头(二分答案+贪心)

P3853 [TJOI2007]路标设置

3.差分优化

当需要修改区间的时候,使用差分优化,使得区间修改变为O(1)

P1083 [NOIP2012 提高组] 借教室

4.前缀和优化

当需要快速求一段区间值的时候,使用前缀和优化,使得区间查询变为O(1)

记得前缀和的经典模型-----最大子段和

102. 最佳牛围栏

上一篇:退役III次后做题记录(扯淡)


下一篇:回溯解八皇后问题