排序+二分
排序
快速排序
基于分治思想
-
确定分界点： \(q[l]\) \(q[l + r >> 1]\) \(q[r]\) 随机
快速排序这道题目的数据已加强，划分中点取左端点或右端点时会超时，改成取中点或者随机值即可
-
调整区间：满足x左边的元素都小于等于x，右边的元素都大于等于x（等于x不影响），所以x不一定在中间位置
初始情况，指针i在最左边的左边一个，指针j在最右边的右边一个的位置
从左向右移动指针i，直到遇到第一个大于x的数，停下来；从右向左移动指针j，直到遇到第一个小于x的数停下来。
交换此时指针i和指针j指向的数
在继续移动指针i和j，直到i和j相遇为止
指针j前面的数都是小于等于x的，指针i后面的数都是大于等于x的
-
递归处理：递归的形式处理左右两段
两个区间：\([l,j]\) \([j+1 , r]\)
易错点：
- quick_sort() 函数里面传入的是 q[] , 因此在swap内也要使用 q[]；
- do - while 循环步进条件 要区分 q[i] 和 q[j]；
- 递归处理的时间前面的右边界为j ， 后面的左边界为 j+1。
快速排序算法模板
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
归并排序
基于分治思想
-
确定分界点，\(mid = l + r >> 1\)，（快速排序取的是数值，归并排序里面确定的是位置）
-
递归排序左边和右边，两边就变成了一个有序的数组
-
归并——将两个有序数组合二为一
双指针法处理两个数列，i指向a数组的0，j指向b数组的0
如果\(a[i] < a[j]\) 将\(a[i]\) 放入新的数组，\(i++\)
如果\(a[j] < a[i]\) 将\(a[j]\) 放入新的数组，\(j++\)
到最后一定是有一个数组已经全部处理完成，还有一个数组没有处理完
将未处理完的数组全部接到新数组的后面
易错点：
- 两个区间 \([l, mid]\) \([mid + 1, r]\) \(i = l, j = mid + 1\)
- 最后将\(tmp\)放入q的时候要注意条件是 \(i = l, i <= r\)
归并排序算法模板
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
二分
整数二分
有单调性就一定可以二分，但是不具有单调性的题目也一定可以二分，二分的本质不是单调性
在区间上定义了某种性质，该性质在左半边满足，在右半边不满足，左右半边不能相交（整数二分）
二分可以寻找性质的边界，既可以选择不满足的边界，也可以选择满足的边界
时刻保证答案在区间内部
-
找中间值\(mid\)： \(mid = l + r >> 1\)
-
先写一个 \(check()\) 函数，然后判断如何更新，如果是 \(l = mid\) ，就要把 \(mid\) 改成 \(l + r >> 1\)
-
每次看更新区间是 \(l = mid\) ( 补上 +1 ) 还是 \(r = mid\)
-
找左区间的右边界
-
\(if( check( mid ) == true )\)
那么mid就在满足性质的区间里面 ， 那么边界答案在 \([mid, r]\) 里面 （包含\(mid\)）
更新：\(l = mid\)
-
\(if( check( mid ) == false )\)
那么边界答案在 \([ l , mid - 1 ]\) 里面
更新：\(r = mid - 1\)
-
-
找右区间的左边界
-
\(if( check( mid ) == true )\)
那么边界答案在$ [ l , mid ]$
更新：\(r = mid\)
-
\(if( check( mid ) == false )\)
那么边界答案在$ [ l , mid ]$
更新：\(l = mid + 1\)
-
注意点：
-
每次选择下一个答案所在的区间
-
二分是否有解和题目有关，和二分模板无关，二分是一定有解的，只需要最后判断二分得到的答案和题目要求的答案是否相同即可
给定数列，求元素的起始位置和终止位置
判断元素的起始位置，\(mid\)满足条件，说明起始位置在\(mid\)前面，\(r = mid\)
判断元素的终止位置，\(mid\)满足条件，说明终止位置在\(mid\)后面，\(l = mid\)
整数二分算法模板
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
//边界答案都存在l指向的位置
浮点数二分
四位小数用 1e-6
六位小数用 1e-8
因为是浮点数二分，不需要考虑边界问题
浮点数二分算法模板
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}