Tag-二分

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2018-12-29 23:04:07 |  0 Comments  |  二分

BUPT大一上学期第三次机考E题核心部分题解 && 二分法讲解。

二分!二分!

引入背景

同学们有没有为上周第三次机考E题困扰呢?
大家都能读懂题目,但是很多同学就很苦恼了:明明我答案是对的,但是为什么我超出时间限制(TLE)了呢?
这是因为大家设计的程序的时间复杂度太高了,在碰到大数据的时候程序无法在规定时间内完成所有运算。
那么这一篇文章就来给大家介绍一种更优的搜索答案的方案————它就是二分查找!

疑惑&解惑

二分?是那个数学高中必修I上、高数上讲的那个二分法吗?
对~!没错就是它!
蛤?二分不是用来找函数近似零点的吗?怎么就成了查找答案了?
nope,二分的功能不只是那一个,它可强大了。在计算机上,我们目前的主要应用是用来二分查找答案。

正题

二分查找,是因为单个查找的时间复杂度太高,让程序查找答案的效率低下,而出现用来替代单步查找的一种方法。它是一种思想,而不能叫做一种算法。
对于二分查找的题目,一般都有一个明显的特征:判断这个解是否能满足所有的题目条件。同学们在设计第三次机考E题的时候,就是逐步判断每一个解是否能满足题意的。其实这种方法从理论上来说是正确的,但是它却做了一些不必要的工作。
我们就以E题来讲解一下二分查找的思路。
首先,我们能确定,最佳答案ans(给战士补充的最大能量)一定在范围1到max{ai}中,其中ai表示第i个能量瓶所含的能量值。
那么我们设答案左区间l = 1,右区间r = max{ai},然后我们用去检索答案区间的中间值mid = (l+r)/2是否能够满足题意。 如果mid能够满足题意,那么说明当前能量值是可行方案,我们就记录下当前的mid的

Title - Artist
0:00