[LOJ10013]曲线


三分法适合求解凸性函数的极值问题

\(设当前求解的区间为[l, r],令lmid = l+\frac{r-l}{3},rmid = r-\frac{r-l}{3},计算f(lmid), f(rmid)\)

将其中函数值更优的点叫做好点,函数值较差的点叫做坏点

最优点与好点会与坏点同侧,据此缩小区间

\(因为a≥0,所以S是开口向上的二次函数,F(x)=\max \{S_{i}(x)\} 也满足单调性,可用三分法求其区间最小值\)


 

发表评论