第一期： 二分(基础算法)

蓝桥杯4月8号就要开始了

还没背熟模板的小伙伴们跟我一起来背模板吧

祝大家4月8号蓝桥杯上岸 ~

不清楚蓝桥杯考什么的点点下方

考点秘籍

想直接看纯模板的见下方

纯模板

想看JavaB组填空题的伙伴们点点下方

填空题

众所周知，二分是蓝桥杯考查热点！

万物皆可二分！！！

下面让我们一起来背二分模板吧！

步骤总结

(1)确定左右边界

l=0,r=n-1

(2)二分

写法1：

while(l<r){
int mid=l+r+1>>1;
if(a[mid]<=x)l=mid;
else r=mid-1;
}

写法2：

while(l<r){
if(a[mid]>=x)r=mid;
else l=mid+1;
}

(3)二分的答案：L

注意：二分处理的是排好序的数组,如果是没有排好序的数组要先用sort()排序

根据题目要求进行变化

模板题：数的范围：
经典真题：
杨辉三角形
统计子矩阵

二分(开背)

import java.util.*;
public class Main{
    static int N=100010;
    static int a[]=new int[N];
    public static void main(String []args){
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int q=scan.nextInt();
        for(int i=0;i<n;i++){
            a[i]=scan.nextInt();
        }
       while(q-->0){
           int x=scan.nextInt();
           int l=0,r=n-1;
           //左边界 l=0
           //右边界 r=n-1

           //满足l<r这一条件则开始二分
           //二分到最后l==r,输出答案即可。
           while(l<r){
               int mid=l+r>>1;
               if(a[mid]>=x)r=mid;
               //当前元素比目标值大，则继续缩小(左移)右边界

               else l=mid+1;
               //否则则增大(右移)左边界
           }
           if(a[l]!=x)System.out.println("-1 -1");
           //找不到则输出-1 -1
           else{
               System.out.print(l+" ");
               l=0;r=n-1;
               while(l<r){
                   int mid=l+r+1>>1;
                   //对于l=mid的情况
                   //mid等于l+r+1
                   // +1一定不要漏掉！！！
                   if(a[mid]<=x)l=mid;
        //二分出的元素大小小于目标值x,说明需要移动左边界。
        //往右方向移动去寻找答案。
                   else r=mid-1;
        //否则则需要移动右边界           
               }
               System.out.println(l);
               //输出二分出的位置l
           }
       }
    }

}

模板背完后，做做例题吧

没时间解释了，快上车！

例题：AcWing 800. 数组元素的目标和

二分

import java.util.*;
public class Main{
    static int N=100010;
    static int a[]=new int [N];
    static int b[]=new int [N];
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int x=sc.nextInt();
        for(int i=0;i<n;i++)a[i]=sc.nextInt();
        for(int j=0;j<m;j++)b[j]=sc.nextInt();
        for(int i=0;i<n;i++){
            int t=x-a[i];
            //看b序列中是否能二分出答案

            //枚举n次
            //看能否在b序列中找到
            int l=0,r=m-1;
            //确定左右边界
           while(l<=r){
               //这里需要枚举b序列的每一个位置
               //l<=r

               //开始二分
               int mid=l+r>>1;
               //二分的中间点
               if(b[mid]==t){//二分的答案

               System.out.println(i+" "+mid);
               //a序列的位置+" "+b序列的位置
                return;
                //唯一解，找到就返回
               }
               else if(b[mid]>t)r=mid-1;
               //mid这个值比t要大
               //b[mid]已经被比较过，所以r=mid-1；
               else l=mid+1;
               //mid这个值比t要小
               //b[mid]已经被比较过，所以l=mid+1;
           } 
        }
    }
}

双指针

//由于两个都是升序数组
//存在单调性
//我们拿上面最小的元素去和下面最大的元素进行匹配
//因为最小的元素都匹配不了，则该序列中后面的元素必定匹配不了。
//如果说最小的元素匹配后的值比x要大，则移动j指针
//j指针移动至和值小于等于x时停止，移动i后面的数能否匹配。
//匹配过程出现和值>=x时，则继续移动j指针。
import java.util.*;
public class Main{
    static int N=100010;
    static int a[]=new int[N];
    static int b[]=new int[N];
    public static void main(String []args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int x=sc.nextInt();
        for(int i=0;i<n;i++)a[i]=sc.nextInt();
        for(int i=0;i<m;i++)b[i]=sc.nextInt();
        for(int i=0,j=m-1;i<n;i++){
           while(j>=0&&a[i]+b[j]>x)j--;
            if(a[i]+b[j]==x){
                System.out.println(i+" "+j);
                return;
            }
    }
}
}

13届javaB组最少刷题数

分析

考点：前缀和+二分

来源

先背一遍模板：

前缀和：

for(int i=0;i<n;i++){
    int a=sc.nextInt();
}
for(int i=1;i<=N;i++){
    s[i]+=s[i-1];

}

二分

(1)情况1

int l= down, r= up
while(l<r){
    int mid=l+r+;
    if(q[mid]>=x)r=mid;
    else l=mid+1;

}

(2)情况2

int l= down, r= up
while(l<r){
    int mid=l+r+1>>1;
    if(q[mid]<=x)l=mid;
    else r=mid-1;
}

最少刷题数

题目描述：

对于每一名学生，请你计算他至少还要再刷多少道题，才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。
全班刷题比他多的学生数不超过刷题比他少的学生数。
换句话说：全班刷题比他少的学生数>=(大于等于)全班刷题比他多的学生数

思路

不会就枚举，挨个去模拟样例，打暴力！
题目是死的，人是活的。
12
比他少的：6，10
比他多的：15，20
需要：0

10
比他少的：6
比他多的：12 15 20
需要：3

15
比他少的：6 10 12
比他多的：20
需要：0

20
比他少的：6 10 12 15
比他多的：20
需要：0

6
比他少的：
比他多的：10 12 15 20
需要：7
我们发现：
像10需要多刷3道题，变为13，将6、12包含进来
像6需要多刷7道题，变为13，将10、12包含进来

多刷题一定可以满足条件,但是少刷题不一定满足条件。

发现具有二段性，我们要找到的是最少满足条件的答案！

这时便想到了二分！

我们通过二分去二分出最少应该刷的总题数

怎么二分？

首先要满足的是题目所给的条件：
全班刷题比他少的学生数>=(大于等于)全班刷题比他多的学生数
那我们要怎么知道刷题数的人数?
用cnt[]数组存一下每种刷题数的人数
再用前缀和处理每段刷题数区间的人数
如果全班刷题比他少的学生数>=(大于等于)全班刷题比他多的学生数，说明不需要刷题，那么直接输出0即可。

剩下的情况需要二分：

当前刷题数 mid
比他刷题数量多的人数即：
cnt[M]-cnt[mid]
比他刷题数量少的人数即：
cnt[mid-1]-1

cnt[mid-1]-1
//当前刷题数为mid
//比他少的便是cnt[mid-1]-1

满足刷题数量比他多的学生小于等于刷题数量比他少的学生
cnt[M]-cnt[mid]<=cnt[mid-1]-1
我们需要继续寻找，缩小范围，即r=mid;
直到找到最少满足条件的刷题数，二分停止。
其他的说明刷题数量不够，则需要往刷题数多的方向继续找：
l=mid+1

二分到最后l==r说明找到最少应该刷的总题数
需要刷的题数(答案)：应该刷的题数l-原本的题数p[i]
即l-p[i]

为什么需要减1？

因为,本来刷题数是小于mid的,包含在mid-1中。
现在变为mid，所以需要减去之前在mid-1区间的自己。

Accode

import java.io.*;
public class Main{
    static int N=100010,M=100000;
    //N开100010防止数组越界
    //M开100000刷题数最多是100000
    static int p[]=new int[N];//每个人的刷题数量
    static int cnt[]=new int[N];//统计不同的刷题数量的人数
    public static void main(String []args) throws IOException
    {
     BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
    PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
     int n=Integer.parseInt(bf.readLine()); 
     String s[]=bf.readLine().split(" ");
     for(int i=0;i<n;i++) {
         p[i]=Integer.parseInt(s[i]);
         //每个人的刷题数量

         cnt[p[i]]++;
         //统计 刷题数量为p[i]的人数
     }

     //某段刷题数区间内的人数
     for(int i=1;i<=M;i++) {
         cnt[i]+=cnt[i-1];
     }

     for(int i=0;i<n;i++) {
    //枚举每个学生的刷题数是否满足     
     if(cnt[M]-cnt[p[i]]<=cnt[Math.max(0, p[i]-1)]) {
     //注意边界：最少不能少于0道刷题数

         //刷题比他多的人数小于等于刷题比他少的
         //那么他就不需要再刷题，直接输出0即可
        pw.print(0+" ");
        continue;   
     }
     //二分出的刷题数量mid
    int l=p[i],r=M;

    while(l<r) {
        int mid=l+r>>1;
    //二分出的刷题数量

    if(cnt[M]-cnt[mid]<=cnt[mid-1]-1) {
        //刷题数量比他多的学生小于等于刷题数量比他少的学生
        //进一步减少刷题数量，r=mid
        r=mid;
    }
    else {
        //否则，说明刷题数量不够，需要多刷题目
        l=mid+1;

    }
    }
    //二分出的l(r)是每个p[i]最少应该刷的总题数
    //需要刷的题数：最少应该刷的总题数-原本的题数
    //即l-p[i]
    pw.print((l-p[i])+" ");

     }

    pw.flush();

}
}

参考资源

https://zhigeng.blog.csdn.net/article/details/128014661?spm=1001.2014.3001.5502

求阶乘

考点：二分+反复整除法

分析

题目问我们的是满足N!的末尾恰好有K个0的最小的N是多少?

思路

阶乘数要想凑出来0必定是有若干个2、5
由于是阶乘2的个数必定是多于5的个数。
因此我们需要去枚举5的个数
没有思路怎么办？

暴力出奇迹，模拟过样例！

10！

10*9*8*7*6*5*4*3*2*1

10、5 总共是2个5
10/5=2

16！

16*15*14*...*10*...*5*...*1

15、10、5总共是3个5
16/5=3
25！

25*...*20*...*15*...*10*...*5

25、20、15、10、5总共有6个5
为什么是6个？
原因在于25可以被拆成5*5，总共是6个5。
所以我们需要反复整除5，这样才能把边界值含5的个数全部统计出来。
最后加上5的个数即可
25/5=5+5/5=6
又如125=5*5*5一共是3个5等于125/5
又如625=5*5*5*5一共是4个5等于625/5

我们通过模拟可以发现：
我们直接对枚举到的数字整除5判断
输出能整除5是k的数字即可

但是看到k的上界为1e18直接枚举必定TLE
题目要求满足N!的末尾恰好有K个0的最小的N
我们需要优化解决,当前N！恰好有k个0。
比N大的N!必定大于K个0,比N小的N！必定小于K个0。

我们直接想到二分来做这道题！！！

怎么二分？

不像最少刷题数那样,满足条件才能进行二分。
这道题直接枚举数字套模板进行二分即可。
因为题目问我们的是最少满足k个0的数字N是多少
不过最后还要检验一下二分出的答案是不是k个0

此外，这题需要考虑一些数据的细节

时间关系,具体看这两个大佬写的博客，写得很棒%%%
博客1
博客2

ACcode

import java.util.*;
public class Main{
    public static void main(String []args) {
        Scanner sc=new Scanner(System.in);
        long k=sc.nextLong();
        long l=1,r=(long)9e18;
        //数据要开大
        //二分
        while(l<r) {

            long mid=l+(r-l)/2;
            //需要再减去l

            //当前的N拆分成5的倍数的个数大于等于k
            //说明需要缩减范围,即r=mid
            if(query(mid)>=k)r=mid;
            //说明不够k需要继续寻找
            else l=mid+1;
        }
        long x=query(r);
        //再查一下N是不是能被拆成k个5
        //可以的话输出r
        //不可以则输出-1
        if(x==k)System.out.println(r);
        else System.out.println("-1");
    }
    static long query(long x) {
        long ans=0;
        //统计能拆分成5的个数
        while(x>0) {
            ans+=x/5;
            //直接让其除以5
            x/=5;
        }
        return ans;
    }
}

提炼

反复整除法：得出某个数的阶乘含a的个数

    static long query(long x) {
        long ans=0;
        //统计能拆分成a的个数
        while(x>0) {
            ans+=x/a;
            //直接让其除以a
            x/=a;
            //再对边界x进行反复整除
            //统计出x还能拆成多少个5/包含多少个5
        }
        return ans;
    }

参考资源

http://t.csdn.cn/2WxI4
https://blog.csdn.net/weixin_57943259/article/details/124206177

看到这里，不妨点个关注