新葡京网址网站建设,泰州整站优化,唐山如何做百度的网站,小说系统+wordpress一、有序和单调
二分本质上是一种更加智能的搜索状态空间的方式#xff0c;他需要状态空间的状态呈现一种“有序的一维数组”的形式#xff0c;然后再进行搜索。所以一开始的排序是无法避免的。
因为二分的写法问题#xff0c;所以应当怎样排序也是有一定讲究的他需要状态空间的状态呈现一种“有序的一维数组”的形式然后再进行搜索。所以一开始的排序是无法避免的。
因为二分的写法问题所以应当怎样排序也是有一定讲究的所以排序的时候就可以定义一定的比较方式。
如果更加细致的讨论的话其实有序只是一个“小条件”比如说很多枚举、搜索类的题目的状态空间也是有序的但是我们却没有用二分法这是因为其核心是适用于二分法的题目它的状态和解之间的关系是单调的如下所示 如左图所示如果我们对于 mid 有了一个讨论我们就可以根据需求去选择往左或者往右右图也是同理我们知道只要小一点就可以将结果置高那么最终的结果就会变成“到底小多少”就是一个很容易解决的问题了。
但是如果状态和结果之间的关系并不单调那么就无法使用二分法了如下所示 左图还可以使用“三分法”但是对于右侧完全没有办法使用“分法”了但是不可否认右图的状态空间也是有序的没准可以用动态规划求解。 二、二分模板
二分一共有两个模板这是因为二分的本质不是通过二分找到“唯一适合“的点二分一般呈现一种“最优化”的特点它要找到是“符合条件”的最大的或者最小的。我们下面的讨论都默认状态空间是增序排列的。
这就导致当 mid 符合条件的时候我们需要判定该往哪一边走了通常情况下我们希望找到约束条件下的最大值那么就应当向 mid 右侧去寻找而当我们希望找到约束条件下的最小值那么就应当向 mid 的左侧去寻找。
在寻找更小的区间的时候有两个原则需要遵守一个是缩小后的区间一定是包括 mid 的是不可以跳过 mid 的这是因为 mid 可能是唯一的“最优值”所以是不能跳过的另一个是一定要在 mid 的基础上进行移动比如说 mid 1, mid - 1 这样的移动这是因为在整数中如果 right - left 1 而不进行移动也就是 left mid, right mid 这就会导致死循环的出现。综上所述我们一般在 mid 符合约束条件的时候利用的是 left mid, right mid 来确保对于 mid 的保留而当 mid 不符合条件的时候进行 left mid 1, right mid - 1 的操作来避免死循环。
同时需要注意二分法的边界条件这个其实有多种写法我选择了 left right 作为循环的条件那么退出的时候就有 left mid right可以选择任何一个索引作为最终结果。
最后还需要注意当搜索不到的情况最后会返回什么这取决于区间缩小时的移动条件如果是 left mid 1那么就会导致在 right 暂停相反则在 left 暂停。
所以模板如下对于选择“最小值”其中 check(int) 函数用于检测是否满足条件
// 求符合约束的最小值
while (left right)
{// 向下取整int mid (left right) 1;// mid 是满足条件的那么向左侧搜索包括 midif (check(mid)){right mid;}// mid 不满足条件向右侧搜索那么最可能满足条件的是 mid 1else {left mid 1;}
} 对于选择“最大值”
// 求符合约束的最大值
while (left right)
{// 向上取整int mid (left right 1) 1;// 如果 mid 满足条件那么向右侧搜索包括 midif (check(mid)){left mid;}// mid 不满足条件向左侧搜索最有可能满足条件的是 mid - 1else{right mid - 1;}
} 对比如下
条目模板 1模板 2目标求出满足约束的最小值求出满足约束的最大值mid 取整方式向 left 取整向 right 取整搜索为空的返回值状态空间 right状态空间 left跳过方向向右 left mid 1向左 right mid - 1三、STL 算法
与上面提出的模板类似的 stl 算法是 lower_bound() 它可以返回第一个大于等于某个值的迭代器也就是这个值的下界位置
// 在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,const T val);
// 在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,const T val, Compare comp); 还有一个类似的函数是 upper_bound() 它可以返回第一个大于某个值的迭代器也就是这个值的上界位置
// 查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const T val);
// 查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const T val, Compare comp); 然后还有一个 equal_range() 返回的是两个迭代器的 pair指明了范围
// 找到 [first, last) 范围中所有等于 val 的元素
pairForwardIterator,ForwardIterator equal_range (ForwardIterator first, ForwardIterator last, const T val);
// 找到 [first, last) 范围内所有等于 val 的元素
pairForwardIterator,ForwardIterator equal_range (ForwardIterator first, ForwardIterator last, const T val, Compare comp); 最后还有一个 bin_search() 返回一个布尔值来确定在有序状态空间中是否有特定值
//查找 [first, last) 区域内是否包含 val
bool binary_search (ForwardIterator first, ForwardIterator last,const T val);
//根据 comp 指定的规则查找 [first, last) 区域内是否包含 val
bool binary_search (ForwardIterator first, ForwardIterator last,const T val, Compare comp); 示意图如下 对于 lower_bound() 其实本质是模板 1 的设计模式找到的是符合条件的最小值其代码如下
template class ForwardIterator, class T // ForwardIterator 前向迭代器
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T val)
{// it 对应 midForwardIterator it;// traits 是萃取机的意思也就是萃取 iterator 里的信息并给到算法// count 是搜索区间步长step 是下一步的步长iterator_traitsForwardIterator::difference_type count, step;// count 的初始值就是 first 和 last 的距离first 对应 leftlast 对应 rightcount distance(first, last);// 步长大于 0与 left right 相同while (count 0){it first;// 二分step count / 2;// 等价于 mid left (right - left) / 2advance(it, step);// 判断 mid 是否满足条件// mid 此时不满足条件if (*it val) // 或者 if (comp(*it,val))对应第 2 种语法格式{// first mid 1first it;// count 约缩小一半count - step 1;}// mid 满足条件缩小步长与使用 last 类似else{count step;}}return first;
} 因为与模式 1 相似所以当不存在相似的值的时候返回的迭代器等于 last 。
upper_bound() 的本质依然是模板 1因为它寻找的是满足大于搜索值的最小值所以代码结构与 lower_bound() 相同。
template class ForwardIterator, class T
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T val)
{ForwardIterator it;iterator_traitsForwardIterator::difference_type count, step;count std::distance(first, last);while (count 0){it first;step count / 2;std::advance(it, step);// 与 lower_bound() 只有这里不同此时表示 mid 不满足大于的条件if (!(val *it)) // 或者 if (!comp(val,*it)), 对应第二种语法格式{first it;count - step 1;}else{count step;}}return first;
} 同样的当不存在相似的值的时候返回的迭代器等于 last 。
equal_range() 本质就是调用了 lower_bound() 和 upper_bound() 如下所示
template class ForwardIterator, class T
pairForwardIterator, ForwardIterator equal_range(ForwardIterator first, ForwardIterator last, const T val)
{ForwardIterator it std::lower_bound(first, last, val);return std::make_pair(it, std::upper_bound(it, last, val));
} binary_search() 调用了 lower_bound() 将返回值与 last 比较并且确定搜索值比最小值first小这是搜索不到的情况
template class ForwardIterator, class T
bool binary_search(ForwardIterator first, ForwardIterator last, const T val)
{first std::lower_bound(first, last, val);return (first ! last !(val *first));
}四、二分验证法
这是一类固定的题型一般呈现“最小最大值”这样的特点并不绝对其本质是其答案的状态空间呈现很好的线性有序性说不定就是个 [0,max)[0, max)[0,max) 的区间我们可以通过二分答案的方法获得 mid 值然后利用这个 mid 值去进行模拟验证如果可以的话那么就二分继续搜索。
比如说下面的这题 [NOIP2015 提高组] 跳石头 题目描述 这项比赛将在一条笔直的河道中进行河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间有 NNN 块岩石不含起点和终点的岩石。在比赛过程中选手们将从起点出发每一步跳向相邻的岩石直至到达终点。 为了提高比赛难度组委会计划移走一些岩石使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制组委会至多从起点和终点之间移走 MMM 块岩石不能移走起点和终点的岩石。 输入格式 第一行包含三个整数 L,N,ML,N,ML,N,M分别表示起点到终点的距离起点和终点之间的岩石数以及组委会至多移走的岩石数。保证 L≥1L \geq 1L≥1 且 N≥M≥0N \geq M \geq 0N≥M≥0。 接下来 NNN 行每行一个整数第 iii 行的整数 Di(0DiL)D_i( 0 D_i L)Di(0DiL) 表示第 iii 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出且不会有两个岩石出现在同一个位置。 输出格式 一个整数即最短跳跃距离的最大值。 样例 #1 样例输入 #1 25 5 2
2
11
14
17
21样例输出 #1 4提示 输入输出样例 1 说明 将与起点距离为 222和 141414 的两个岩石移走后,最短的跳跃距离为 444(从与起点距离 171717 的岩石跳到距离 212121 的岩石,或者从距离 212121 的岩石跳到终点)。 数据规模与约定 对于 20%20\%20%的数据0≤M≤N≤100 \le M \le N \le 100≤M≤N≤10。 对于 50%50\%50% 的数据0≤M≤N≤1000 \le M \le N \le 1000≤M≤N≤100。 对于 100%100\%100%的数据0≤M≤N≤50000,1≤L≤1090 \le M \le N \le 50000,1 \le L \le 10^90≤M≤N≤50000,1≤L≤109。 可以看到这个题目的答案空间是在 [0,L)[0, L)[0,L) 之间的虽然题目看着很复杂但是如果考虑用二分的方法去做对于每一个 mid 值的检验是很容易进行模拟的如下所示
#include bits/stdc.husing namespace std;int l, m, n;
int d[50005];// 对于传入的 mid进行模拟检验
bool check(int step)
{int cnt 0;int pre 0;for (int i 0; i n; i){// 如果距离小于 step说明需要将这个石头移除if (d[i] - pre step){cnt;}// 否则就更新前一个木桩else{pre d[i];}}// 最终的结果是移除的石头不能多余 mreturn cnt m;
}int main()
{cin l n m;for (int i 0; i n; i){cin d[i];}d[n] l;int left 0, right l 1;// 因为是求解最大值所以采用的是模板 2while (left right){int mid (left right 1) 1;if (check(mid)){left mid;}else{right mid - 1;}}cout left;return 0;
} 需要注意的是在 check() 中因为采用的是模拟方法所以可能会导致复杂度比较高所以当模拟到失败的时候需要进行减枝优化。比如说洛谷上的这道题目 https://www.luogu.com.cn/problem/P3853 它的格式基本上与前面的题目相同但是在 check() 上进行减枝
bool check(int step)
{int cnt 0, pre 0;for (int i 0; i n;){if (d[i] - pre step){cnt;pre step;}else{pre d[i];i;}// 减枝if (cnt m){return false;}}return true;
}五、实数二分
实数二分的模板要更加容易记忆唯一需要注意的就是精度问题因为控制不好精度很容易导致死循环似乎到了 1e-7 左右就容易 tle这可能是由于双精度浮点数的精度相比较大导致的所以一般采用 1e-6一定要注意题目中的描述模板如下
double left 0, right 1e10;
while (left 1e-6 right)
{double mid (left right) / 2;if (check(mid)){left mid;}else{right mid;}
}
