二分查找

1.list与set的区别与优缺点：循环速度:list最适合做固定长度的遍历，而且有顺序。set是无序的，list转换为set会乱序，若用set给list去重，转化为list时须用原list的index排序：new_list.sort(key=old_list.index)。所以这种循环尽量用list查询速度:set>list,set查询的key都是ha......

原题链接：https://www.luogu.com.cn/problem/P3853题意解读：相邻路标的最大距离即空旷指数，空旷指数越小，用的路标越多，因此可以根据空旷指数将使用路标情况分成两类：路标数<=K，路标数>K，对空旷指数进行二分即可。解题思路：二分的判定条件为，给定空旷指数，计算需要的路标数只需遍历每两......

原题链接：https://www.luogu.com.cn/problem/P2678题意解读：最短跳跃距离越大，要移走的石头就越多，因此可以根据最短跳跃距离的不同把情况分为两类：移走的石头数<=M、移走的石头数>M，对最短跳跃距离二分即可。解题思路：二分的判定条件如下：对于给定最短跳跃距离，需要计算移走的石头数，......

在算法题中经常会出现搜索的题目，如果使用暴力搜索在数据量较大时会超时，（如\(10^5\)数量级时\(O(n^2)\)就会超时，\(O(nlogn)\)则通常不会），因此常用二分搜索等进行优化。虽然stl库中关于二分搜索的接口很好用，很适合区间二分搜索，但我们仍需掌握C++实现二分搜索，“虽然这是一个简单的算法......

原题链接：https://www.luogu.com.cn/problem/P2440题意解读：切出来的长度越短，则段数越多，可以通过二分长度来解决。解题思路：二分的关键在于判定条件，此题就是对二分到的长度计算可以切割的段数，如果段数大于等于k，则满足要求，可以继续加大长度。注意点：1、计算切割出来的段数是累加：每......

1.思想对于一个已排序数组，找到一个点，使得数组被分为两部分，即此点左部和右部（点在左部或右部中的一个），比如数组中小于等于某数x的部分与大于的部分；对于整数二分而言两个范围之间是没有空隙的，即左部分的边界x的下一个数一定在右部分。我们可以根据题目选择多种方法二分数组，大类上分......

二分查找模板总结二分查找是一种在有序数组中查找某一特定元素的搜索算法。元素集合有顺序，元素性质有分界点，二分法就可以用来求分界点，并不一定要求集合中元素是不重复的。算法思路：假设目标值在闭区间[left,right]中，每次将区间长度缩小一半，当left=right时，我们就找到了......

原题链接：https://www.luogu.com.cn/problem/P1678题意解读：要计算不满意度之和的最小值，就要保证每个人的不满意度最小，即选择的学校录取分数-学生分数之差的绝对值最小。解题思路：如何在学校录取分数中找与学生分数最接近的呢？有三种可能：1、学生分数在录取分数中存在相等的2、学......

原题链接：https://www.luogu.com.cn/problem/P1102题意解读：寻找A-B=C的数对数量，C大于0，B一定比A小，枚举B，找A是否存在即可。解题思路：先将数据由小到大排序，接下来介绍两种方法：二分、双指针1、二分枚举第1~n-1个数，作为B，寻找A=B+C的数量，只需要通过二分查找第一A和最后一个A的位置l、......

传送门解题思路直接二分能干掉的人数，然后check函数枚举所有区间，因为m很小，所以可以用m个ST表预处理每个区间对应每个属性的最大值。一是需要注意二分的写法，而是注意check(0)时候的特判。AC代码#include<iostream>#include<algorithm>#include<cmath>#include<cstdio>#......