BUPT大一上学期第三次机考E题核心部分题解 && 二分法讲解。
文章来自
Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)
Home
About Me
Tags
Archives
## 二分!二分! ## 引入背景 同学们有没有为上周第三次机考E题困扰呢? 大家都能读懂题目,但是很多同学就很苦恼了:明明我答案是对的,但是为什么我超出时间限制(TLE)了呢? 这是因为大家设计的程序的时间复杂度太高了,在碰到大数据的时候程序无法在规定时间内完成所有运算。 那么这一篇文章就来给大家介绍一种更优的搜索答案的方案————它就是二分查找! ## 疑惑&解惑 二分?是那个数学高中必修I上、高数上讲的那个二分法吗? 对~!没错就是它! 蛤?二分不是用来找函数近似零点的吗?怎么就成了查找答案了? nope,二分的功能不只是那一个,它可强大了。在计算机上,我们目前的主要应用是用来二分查找答案。 ## 正题 二分查找,是因为单个查找的时间复杂度太高,让程序查找答案的效率低下,而出现用来替代单步查找的一种方法。它是一种思想,而不能叫做一种算法。 对于二分查找的题目,一般都有一个明显的特征:判断这个解是否能满足所有的题目条件。同学们在设计第三次机考E题的时候,就是逐步判断每一个解是否能满足题意的。其实这种方法从理论上来说是正确的,但是它却做了一些不必要的工作。 我们就以E题来讲解一下二分查找的思路。 首先,我们能确定,最佳答案ans(给战士补充的最大能量)一定在范围1到max{$a_i$}中,其中$a_i$表示第i个能量瓶所含的能量值。 那么我们设答案左区间l = 1,右区间r = max{$a_i$},然后我们用去检索答案区间的中间值mid = $(l + r) / 2$是否能够满足题意。 如果mid能够满足题意,那么说明当前能量值是可行方案,我们就记录下当前的mid的值作为当前答案存入ans,`ans = mid;`,然后去检索更大的值是否可行,也就是将mid+1赋值给l,继续去搜索。 当然,如果mid不能够满足题意,那么说明当前的能量值是不可行的方案,我们就不用记录当前的答案,然后我们去搜索更小的答案是否可能能行,也就是将mid-1赋值给r。 这样做下去,我们的答案区间在不断缩小,我们也就能够不断逼近最佳的解。直到我们将区间长度缩小为0,也就是$r<l$,那么当前ans中记录的值就是我们要求的最佳答案了。 以上过程我们通常使用while循环去做,直到满足$r<l$,我们就跳出while循环,此时ans中存储的值便是我们要的答案。 那么接下来我们附上核心部分代码(check函数就是判断这个答案是否可行,这个就不放出来了): while(l <= r){ mid = (r + l) / 2; if(check(mid)){ l = mid + 1; ans = mid; } else r = mid - 1; } 总结一下,二分查找的核心思路是:确定答案所在区间$l,r$ ,计算区间中间值$mid$,检查中间值$mid$是否满足题意(也就是我们代码里的check函数(这个函数需要大家自行编写)),若满足,则记录答案$ans$ = $mid$,如不满足则不记录答案,然后将区间缩小(至于往哪边缩小要看题目,可以去luogu上看看类似的简单二分题)。直到区间长度为0,跳出while循环,输出答案$ans$。 如果我们单步检索答案,我们的程序的时间复杂度是O(m*max{$a_i$}),但如果我们使用二分查找的话,我们的程序的时间复杂度就成为了O(m*$log_2max{a_i}$)了,这样时间复杂度就下降了不少! ## 需要注意的地方 并不是所有检索答案的题目都能使用二分查找的。我们称可以使用二分查找的题目的数学模型"满足二分性"。事实上确实是有一些题目是不满足二分性的。 满足二分性的定义:我们称一个题目的数学模型满足二分性,当且仅当找到一个值满足题目条件,且小于它的所有值或者大于它的所有值都能满足题目条件。 如果不满足上述的条件,那么我们说这个题目不满足二分性,也就不能使用二分查找来优化检索答案。这样的题目有很多,而且大多数会长得很像使用二分的题目(比如求XXX的最大值的理论最小值,大概95%的题目是用二分查找,剩下5%的题目是用贪心思想或者其他的算法去做),这时候就需要大家仔细判断了。 很显然,我们机考的E题是一个满足二分性的题目,是可以进行二分查找的。 ## 后言 好啦,关于二分查找的讲解就到这里啦,当然其实C++里面是有二分查找的库函数模板的,但是还是推荐大家使用自己手写的二分查找,因为这个二分查找更加灵活。 大家如果想练习二分查找的题目的话,可以到luogu上面直接找题目分类->二分 里面的题目。 最后祝大家计导期末考顺利8。
Pre:
[转载]6 个技巧,提升 C++11 的 vector 性能
Next:
Codeforces Round#528 div2 F. Rock-Paper-Scissors Champion
COMMENT
Sign in
to leave a comment.
No Leanote account ?
Sign up now
.
0
comments
More...
Title
-
Artist
0:00
No Leanote account ? Sign up now.