是一篇拖延症晚期拖了好久才开始写的学习笔记
大概记一下关于二分和分治的感想吧
二分
二分也没啥好说的(况且作为蒟蒻也只会写二分答案),基本套路就是二分答案在检查一下答案,把求值问题转化为判定性问题
值得注意的是:关于限定最大值求最小和限定最小值求最大应当有两种不同的处理
//限定最小值求最大
while (l < r){
mid = l + ((r - l + 1) >> 1);
if (!check(mid)) r = mid - 1;
else l = mid;
}
return l;
//限定最大值求最小
while (l < r){
mid = l + ((r - l) >> 1);
if (!check(mid)) l = mid + 1;
else r = mid;
}两者本质的共同点在于:
- 当区间长为偶时,一定要将区间平分,否则在区间长足够小的时候会陷入死循环
- 当
mid可以满足约束时,一定要将它包含在下一个检查的区间里,否则若mid为解时程序将求不出解
此外:
二分查找配合前缀/后缀和数组进行使用有奇效
分治
挺广泛的一个操作,包括线段树在内许多东西都是利用的分治的思想.这里记两个印象比较深刻的分治
二分的分治
经典的就是平面最近点对问题.平面问题反正先离散就是了.接着对x值分成两部分–这是没道理的暴力的分.当分至只有一个点时就得到一个当前最优状态maxint
而分治的核心在于合并操作:整个算法的复杂度就是合并复杂度加上一个logN.对于平面最近点对问题的合并暴力又不失效率:对于割线两边距离不大于当前最优值的点进行配对,查看是否有更优解.(此外除了x值的限定还可以对y值进一步限定).复杂度上看它是一个N^2的合并,但实际上这个"暴力"的算法效率很高
总的来说,如果能写出一个高效的合并,分治可以将一个N降为logN
快排的分治
这种分治用于求第k大问题等.和其它分治相比,它的特色在于:没有一个固定的mid值,它只有一个随机取的mid的价值,并通过比较这个价值的大小从两边向中间逼近,从而求出mid值,用于确定下一个区间.也就是二分的分治的反向操作
当然,由于鄙人比较弱,所以不知道这个操作除了求第k大之外还有什么用