第一期： ✨ 二分(基础算法)
蓝桥杯4月8号就要开始了 ❗️ ❗️ ❗️
还没背熟模板的小伙伴们跟我一起来背模板吧 💪 💪 💪
祝大家4月8号蓝桥杯上岸 ☀️ ~
往期精彩回顾：
考点秘籍
蓝桥杯 Java 省赛 B 组(初赛)填空题
Java快读快写
java常用数组拷贝
常用Java竞赛基础技能总结
欢迎大家评论交流关注收藏~~~
众所周知，二分是蓝桥杯考查热点！
万物皆可二分！！！
下面让我们一起来背二分模板吧！
步骤总结
(1)确定左右边界
l=0,r=n-1
(2)二分
写法1：
写法2：
(3)二分的答案：L
注意：二分处理的是排好序的数组,如果是没有排好序的数组要先用sort()排序
根据题目要求进行变化
模板题：数的范围：
经典真题：
杨辉三角形
统计子矩阵
二分(开背)
模板背完后，做做例题吧 👊
🌟没时间解释了，快上车！蓝桥杯java基础训练;💫
例题：AcWing 800. 数组元素的目标和
二分
双指针
13届javaB组最少刷题数
分析
考点：前缀和+二分
来源
先背一遍模板：
前缀和：
二分
(1)情况1
(2)情况2
最少刷题数
题目描述：
对于每一名学生，请你计算他至少还要再刷多少道题，才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。
全班刷题比他多的学生数不超过刷题比他少的学生数。
换句话说：全班刷题比他少的学生数>=(大于等于)全班刷题比他多的学生数
思路
不会就枚举，挨个去模拟样例，打暴力！
题目是死的，人是活的。
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包含进来
多刷题一定可以满足条件,但是少刷题不一定满足条件。
发现具有二段性，我们要找到的是最少满足条件的答案！
这时便想到了二分！
我们通过二分去二分出最少应该刷的总题数
怎么二分？
首先要满足的是题目所给的条件：
全班刷题比他少的学生数>=(大于等于)全班刷题比他多的学生数
那我们要怎么知道刷题数的人数?
用数组存一下每种刷题数的人数
再用前缀和处理每段刷题数区间的人数
如果全班刷题比他少的学生数>=(大于等于)全班刷题比他多的学生数，说明不需要刷题，那么直接输出0即可。
剩下的情况需要二分：
当前刷题数
比他刷题数量多的人数即：
比他刷题数量少的人数即：
满足刷题数量比他多的学生小于等于刷题数量比他少的学生
我们需要继续寻找，缩小范围，即
直到找到最少满足条件的刷题数，二分停止。
其他的说明刷题数量不够，则需要往刷题数多的方向继续找：
二分到最说明找到最少应该刷的总题数
需要刷的题数(答案)：应该刷的题数l-原本的题数p[i]
即
为什么需要减1？
因为,本来刷题数是小于的,包含在中。
现在变为，所以需要减去之前在区间的自己。
Accode
参考资源
https://zhigeng.blog.csdn.net/article/details/?spm=1001.2014.3001.5502
求阶乘
考点：二分+反复整除法
分析
题目问我们的是满足N!的末尾恰好有K个0的最小的N是多少?
思路
阶乘数要想凑出来0必定是有若干个2、5
由于是阶乘2的个数必定是多于5的个数。
因此我们需要去枚举5的个数
没有思路怎么办？
暴力出奇迹，模拟过样例！
10！
10、5 总共是2个5
16！
15、10、5总共是3个5
25！
25、20、15、10、5总共有6个5
为什么是6个？
原因在于25可以被拆成5*5，总共是6个5。
所以我们需要反复整除5，这样才能把边界值含5的个数全部统计出来。
最后加上5的个数即可
又如一共是3个5等于
又如一共是个5等于
我们通过模拟可以发现：
我们直接对枚举到的数字整除5判断
输出能整除5是k的数字即可
但是看到k的上界为1e18直接枚举必定
题目要求满足N!的末尾恰好有K个0的最小的N
我们需要优化解决,当前N！恰好有k个0。
比N大的N!必定大于K个0,比N小的N！必定小于K个0。
我们直接想到二分来做这道题！！！
怎么二分？
不像最少刷题数那样,满足条件才能进行二分。
这道题直接枚举数字套模板进行二分即可。
因为题目问我们的是最少满足k个0的数字N是多少
不过最后还要检验一下二分出的答案是不是k个0
此外，这题需要考虑一些数据的细节
时间关系,具体看这两个大佬写的博客，写得很棒%%%
博客1
博客2
ACcode
提炼
反复整除法：得出某个数的阶乘含a的个数
参考资源
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/20705.html