写在前面
解题的三大步骤
1条件提取/需求分解
2模块化处理
3优化
一.二分
1. 二分查找（ nlogn ）
STL:
-
lower_bound(begin, end, x)：
一个大于等于x的值的地址
-
lower_bound(begin, end, x, greater):
最后一个小于x的值的地址
-
upper_bound(begin, end, x):
第一个大于x的值的地址
（T(n) = T(\frac{n}{2}) +1）
2. 二分答案( \text{判断复杂度} \times \log (\text{数据范围}）)
-
1 单调性—>可行性
-
2范围已知
-
3明确知道某答案是否可行
二.分治
解题步骤:
- 何为边界
- 如何分解
- 如何合并
例子：
- eg1.归并排序(求逆序对个数)
- eg2.快速排序
- eg3.静态序列第$k$小
- eg4.P1429 平面最近点对
- eg5.P1228 地毯填补问题
小组成员：邵品渊， 邵品砚， 顾天泽， 蒋佳成