二分练习plus - 二分
二分的理论基础
二分的作用
- Q：二分有什么作用？
- A：二分可以在 \(O_{\log n}\) 的时间内找到特定的值。
二分的原理
-
Q：二分的原理是什么？
-
A：二分的本质是分治，把从一个大区间里找东西的问题根据找的东西的大小分成两半，只查找答案可能在的范围，不可能在的范围不管。
-
Q：时间复杂度为什么是 \(O_{\log n}\) ？
-
A：因为每次将区间缩小到原来的一半，共缩小 \(\log n\) 次到 \(1\) 。
-
Q：二分的递归写法和循环写法区别在哪里？
-
A：二分的递归写法如下：
void bs(int left,int right,int t){ int mid=left+right>>1; if(left>right) return; // if(arr[mid]==t) return; //用于找第一个出现的 if(arr[mid]<t) bs(mid+1,right,t); else bs(left,mid-1,t); }循环写法如下：
void bs(int l,int r,int t){ int left=l,right=r; while(left<=right){ int mid=left+right>>1; if(arr[mid]==t) return; if(arr[mid]<t) left=mid+1; else right=mid-1; } }它们之间的区别在于，循环写法更简单好写，递归容易死递归、爆栈等，所以用循环而一般不用递归。
-
Q：找第一个大于等于某个数的值和找最后一个小于等于某个数的值，有什么区别？
-
A：
- 在二分时，一个是答案符合要求先保留，看能不能更大，另一个是看能不能更小。
- 找最后一个小于等于某个数的值时，要注意
mid向上取整，不然分得不够均匀会死循环。
二分的注意事项
- 使用二分时务必保证数据满足单调性。
- 注意实数二分时要设置
eps因为left和right一般不会相遇。 - 注意
mid的不同写法一般是mid=left+right>>1在实数中是mid=(left+right)/2.0如果有越界风险可以写(left>>1)+(right>>1)。
NKOJ 1190 何老板的淘宝店2.0
思路：二分模板
实现方法：
lower_bound(arr+1,arr+1+n,需要查找的数)。
NKOJ 1048 【分类练习4.分治法】求方程的根
思路：用二分求方程的解。
实现方法：
- 在实数中二分方程的解。
- 如果满足方程，输出。
注意事项：
- 开始时注意判断是不是
NO。
NKOJ 3592 人数统计
法一
思路：map 。
实现方法：
- 把每个 \(k\) 都用
map记录下来。 - 问什么输出什么。
法二
思路：二分。
实现方法：
- 先给数组排序。
- 每个询问搜第一个大于 \(x\) 的值，和最后一个小于等于 \(x\) 的值，然后做差。
NKOJ 3593 工资统计
与NKOJ 3592完全相同。
NKOJ 1934 外地人
法一
思路：map 。
实现方法：
- 把每个字符串都用
map记录下来。 - 问什么输出什么。
法二
思路：二分。
实现方法：
- 先给按字典序排序。
- 每个询问用二分询问的字符串，输出对应的字符串。
注意事项：在用字符串 cin 时，一定要加 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) 。
NKOJ 3144 何老板的淘宝店3.0
思路：找数，如果没有就是第一个大于等于它的和最后一个小于等于它的比较，谁接近用谁
二分答案
二分答案的使用场景
- Q：为什们要用二分答案？
- A：因为有的题目中，答案不能通过贪心直接计算，而需要循环枚举检查其是否可行，循环速度很慢，所以使用二分。
check 函数怎么写
- Q：
check函数的实现思路是什么？ - A：根据你二分的答案，带入题目场景中，检查符不符合题目给定的限制。注意：答案是不是最大 / 最小不是
check函数检查的地方。
NKOJ 3145 洗衣服
思路：二分答案
实现方法：
- 二分所需的最少时间。
check函数：如果规定时间内能自然烘干就跳过，否则就给计数变量加上当前衣服用散热器烘的时间。
注意事项：
- 注意在开始时将
k减 \(1\) 。
课件例题 砍甘蔗
思路：二分答案
实现方法：
- 二分最长的甘蔗最短的长度。
check函数：从头开一段新的，只要大于要求的甘蔗长度就新开一段，检查 \(m\) 段能不能装完。
NKOJ 1192 收入计划
与上题完全相同。
NKOJ 1007 书的复制
思路：与砍甘蔗相同，考虑如何输出。
实现方法：
- 先采用砍甘蔗测略，找到最大的最小是多少。
- 然后用一次
check函数的代码，把详细的段分出来。 - 注意：题目中说了如果有多解，要让前面的人抄的尽量少 所以需要调整策略。
- 把整个数组翻转。
- 输出 \(i\) 时，全部输出 \(n-i+1\) 。
- 从小到大输出。
洛谷 1824 进击的奶牛
思路：类似于砍甘蔗，区别在于一个是最大的最小，一个是最小的最大。
实现方法：
- 调整二分，将其改为求最小的最大。
check函数完全相同。
二分小技巧
- 一般题目中说到 “最大 / 小值最小 / 大”，可以考虑二分答案。
- 一般题目如果是二分答案，就问什么二分什么。