三分法
三分   发布于 2019-02-03   458人围观  0条评论
三分   发表于 2019-02-03   458人围观  0条评论

三分法

我们已经学过有序序列查找元素的二分法了,那么这次来学一下三分法。
三分法,故名思义,就是把一个区间分成三份。
但是这三分法是用来干什么的呢?
三分法是用来求解单峰函数型(凸型序列,包括上凸和下凸)查找元素问题最值的有力手段。

(图片转自chenxiaoran666的博客)

三分的核心思路如下: 对于当前的区间[l,r],求出midl = (l+r)/2,midr = (midl+r)/2,比较f(midl)与f(midr)的值哪个更接近于最值,并根据结果确认下一个搜索区间是[l,midr]还是[midl,r],直到l>=r。


示例代码

我们以上凸序列为例

int find(int l,int r){
    if(l >= r)return l;
    int midl = (l+r) >> 1;
    int midr = (midl + r) >> 1;
    if(a[midl] > a[midr])
        return find(l,midr);
    else return find(midl,r);
}​

当然也是可以写成迭代形式的,如下:

while(l < r){
    int midl = (l + r) >> 1;
    int midr = (midl + r) >> 1;
    if(a[midl] > a[midr])
        r = midr;
    else l = midl;
}​

虽然很少用,但是这种方法还是会有些用的,例如凸包。

如果各位官爷学到的话,请在我的QQ点个赞吧,QQ932901730(厚脸皮)。

上一篇: BUPT训练-Codefoces325E Red Button

下一篇: 数位DP & BZOJ1026[SCOI 2009]windy数题解

立即登录,发表评论
没有帐号?立即注册
0 条评论