三分算法

前言

在自从gdoi2016被第一题的三分虐了后，再次接触三分，其实不难。 三分算法解决凸形或者凹形函数的极值。

流程

令lmid=l+r−l3,rmid=r−r−l3 当lmid在函数上的值小于rmid时将l更新为lmid ； 当rmid在函数上的值小于lmid时将r更新为rmid ； 直到 l>=r 。

原理

当lmid在函数上的值小于rmid时，易证lmid一定在极值的左边，所以将l更新为lmid 。 同样 当rmid在函数上的值小于lmid时，易证rmid一定在极值的右边，所以将r更新为rmid 。 通过这样来一次次缩小(l,r)的范围。

code

double l=0,r=n; while(l+0.001<=r) { double mid1=l+(r-l)/3,mid2=r-(r-l)/3; if(a[mid1]<a[mid2]) l=lmid; else r=rmid; }

推荐一道好题， 【NOIP2016提高A组模拟8.14】传送带