二分法介绍以及例题分析

最近几天都在学习acwing的蓝桥杯算法题，还是有点难度的，这期就给大家分享几个二分法的经典题趴~

多多点赞哦~

二分法1.数的范围

题目描述

输入格式输出格式数据范围输入样例：输出样例： 思路分析代码实现 2.机器人跳跃问题

题目描述

输入格式输出格式数据范围输入样例1：输出样例1：输入样例2：输出样例2：输入样例3：输出样例3： 思路分析代码实现提醒 3.分巧克力

题目描述

输入格式输出格式数据范围输入样例：输出样例： 思路分析代码实现

通过多次将查找范围分成一半实现快速查找的一种方法。

二分法有以下几个步骤

1.先确定目标元素所在区间

2.确定临界点(一定要是满足条件和不满足条件的分界点) 非常重要！！!

3.通过不断二分确定结果。

其中第二步我个人觉得是最重要的，一旦出错就有很大概率无法得出正确答案，详细我们可以在以下几个题中看到。

给定一个按照升序排列的长度为 n 的整数数组，以及 q个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 00 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

第一行包含整数 n 和 q，表示数组长度和询问个数。

第二行包含 n个整数（均在 1∼100001∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。

共 q行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤10000

6 3
1 2 2 3 3 4
3
4
5

3 4
5 5
-1 -1

和上述步骤一样，先确定区间，然后确定临界点。

这题要求我们求出目标元素的第一个位置和最后一个位置，我们看作是左端点和右端点

作为临界点，必须是满足条件的分界点，左端点应当满足左边元素全不满足条件，而满足条件的区间在右边，故q[mid]>=begin作为判断条件，而求右端点就相反，这里要细细想，想明白了就豁然开朗了[doge]

#include 
#include 
#include 
#include 

using namespace std;

const int N = 100010;

int n;      //数组元素个数
int m;      //几组数据
int q[N];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i =0; i < n; i++)
    {
        scanf("%d",&q[i]);
    }
    
    for(int i = 0;i=begin)
            {
                r=mid;
            }
            else l=mid+1;
        }
        
         if(q[l]==begin)  
        {
             r=n-1;
             cout< 
2.机器人跳跃问题 
题目描述 
机器人正在玩一个古老的基于 DOS 的游戏。
 
游戏中有 N+1 座建筑——从 0 到 N 编号，从左到右排列。
 
编号为 0 的建筑高度为 0 个单位，编号为 i的建筑高度为 H(i) 个单位。
 
起初，机器人在编号为 0的建筑处。
 
每一步，它跳到下一个（右边）建筑。
 
假设机器人在第 k 个建筑，且它现在的能量值是 E，下一步它将跳到第 k+1 个建筑。
 
如果 H(k+1)>E，那么机器人就失去H(k+1)−E 的能量值，否则它将得到 E−H(k+1) 的能量值。
 
游戏目标是到达第 N 个建筑，在这个过程中能量值不能为负数个单位。
 
现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？
 
输入格式 
第一行输入整数 N。
 
第二行是 N 个空格分隔的整数，H(1),H(2),…,H(N)H(1),H(2),…,H(N) 代表建筑物的高度。
 
输出格式 
输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。
 
数据范围 
1≤N,H(i)≤1051≤N,H(i)≤105,
 
输入样例1： 
5
3 4 3 2 4
 
输出样例1： 
4
 
输入样例2： 
3
4 4 4
 
输出样例2： 
4
 
输入样例3： 
3
1 6 4
 
输出样例3： 
3
 
思路分析 
 
 
开始看到这道题，想了四十多分钟，丝毫看不出和二分有什么关系，只想到用递推来做出来，看了y总视频才恍然大悟，原来二分竟然是这样用的！！！
 
 
这道题和所有二分思路一样，先确定区间再找临界点。
 
 
在找区间和临界点之前我们要先确定对象是什么，这道题的对象应当是E0，即满足条件的最小能量值，而不是位置或序号。
 
 
当我们当前能量大于等于E0，就能够通过，反之则不能通过，因此E0作为临界点很好地满足了二分法。
 
 
而E最大值是建筑的最大高度，故它的区间可看作是[0,100000].
 
 
通过观察我们可以发现E变化后的值总满足 E` = 2E - H(k+1)
 
 
故我们可以通过递推看当前E是否可以通过游戏；
 
 
代码实现 
#include 
#include 
#include 
#include 

using namespace std;

const int E = 100010;         //最大能量

int N;                        //建筑数
int H[E];
int l;
int r;
int mid;


bool check(int m)
{
    for(int i =0;i< N;i++)
    {
        m = 2*m - H[i];
        if(m >= 1e5)  return true;
        if(m<0)  return false;
    }
    return true;
}

int main()
{
    scanf("%d",&N);
    
    for(int i =0; i< N;i++)
    {
        scanf("%d",&H[i]);
    }
    
     l = 0;
     r = E;
     
     while(l < r)
     {
         mid = l + r >>1;
         if(check(mid))               //如果当前E能够通过游戏
         {
             r = mid;
         }
         else l = mid + 1;
     }
     
    printf("%dn",r);
     
    return 0;
}

 
提醒 
 
 
这里要注意以下，我求mid时用的是>>1，这个是向上取整的，例如3 + 6 >>1为5,而3 + 6/2的值为4，而且>>的速度要明显快于/
 
 
我用/的时候就通不过···
 
 
3.分巧克力 
题目描述 
儿童节那天有 K 位小朋友到小明家做客。
 
小明拿出了珍藏的巧克力招待小朋友们。
 
小明一共有N 块巧克力，其中第 ii 块是 Hi×Wi的方格组成的长方形。
 
为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
 
切出的巧克力需要满足：
 
形状是正方形，边长是整数大小相同
 
例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。
 
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
 
输入格式 
第一行包含两个整数 N 和 K。
 
以下 N 行每行包含两个整数 Hi 和 Wi。
 
输入保证每位小朋友至少能获得一块 1×1 的巧克力。
 
输出格式 
输出切出的正方形巧克力最大可能的边长。
 
数据范围 
1≤N,K≤1051≤N,K≤105,
 1≤Hi,Wi≤1051≤Hi,Wi≤105
 
输入样例： 
2 10
6 5
5 6
 
输出样例： 
2
 
思路分析 
 
 
求的是巧克力能切得的最大边长。
 
 
题目暗示的条件是所有小朋友的巧克力都是一样大。
 
 
可以这样来想，将每块巧克力切成某个边长为u的小巧克力，看总共可以切得多少个，看最终个数是否大于小朋友的人数。
 
 
我们可以以边长作为区间，小朋友的所需的总巧克力数作为临界值，只有能切得的巧克力个数大于人数才满足。
 
 
代码实现 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 100010;
int n,k;
int H[N];
int L[N];

bool check(int u)
{
    int sum = 0;
    for(int i =0;i=k)
    return true;
    return false;
}


int main()
{
    
    scanf("%d%d",&n,&k);
    for(int i =0;i>1;
        if(check(mid))
        {
            l = mid;
        }
        else r = mid -1;
    }
    cout<