二分法,三分法,尺取法

作者: qwq 分类: 算法 发布时间: 2017-07-14 16:20

二分法

二分法的主要内容就是对一个单调的区间进行二分,可以在很低的时间内快速确定答案的位置。

首先确定一个左端点和右端点,即可以得到一个中点mid=(L+R)/2 ,二分之后需要对中间点进行judge,进行正义的审判,确定该点是否可行。然后根据judge的结果缩小区间。

每次二分即可以把区间缩小一半。

题目链接

题目链接

尺取法

尺取法是模拟的虫子的蠕动。可以降低不必要的计算量。

在某些题目中可以将复杂度为n^2降低到n

题目链接


三分法

三分法不同与二分法在于三分法适用于有“山峰”的题目,即题目的解是先升高,然后到一个最高点,之后再降低。

题目的目的就是求那一个最大值。

这时候还是需要一个L端点和R端点,但是需要两个mid点,一个mid点是(L+R)/2

另外一个mid2点是(mid+R)/2 即是3/4点。

这样通过比较两个mid点的大小,即可推断出来山峰的位置,从而缩小区间。

经过多次逼近后,即可求得题解。

题目链接

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注