【模板】三分法

题目

洛谷P3382【模板】三分法

题解

三分法用于求单峰或单谷函数的极值,并且函数极值的两边必须严格单调。流程:类比二分,设l,r,lmid,rmid指针,其中lmid,rmid是[l,r]的三等分点。此处以单峰函数为例,若f[lmid]<f[rmid],则lmid,rmid同在极值左侧或在极值两侧,则极值在lmid右侧;若f[lmid]>f[rmid],同理,极值在rmid左侧;若f[lmid]=f[rmid],则两指针分在极值两侧。

代码

Subscribe
提醒
guest
2 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月13日 上午9:35

【小白解析】
此题答案比较好理解,本质上是通过[l,r]区间上的两个三等分点不断压缩,直至lmid与rmid基本相等为止。
此外需注意第11行和31行的配合:多项式系数实际上是从低到高被依次安放在数组内的。
当然,熟知微积分概念的解题者也可以通过求原函数导数解题:对输入函数取到后,用二分法在[l,r]上寻找零点,并且使x精确度符合题目要求。(具体做法为取中间值mid,若大于0,则使l=mid;若小于0则时r=mid,操作至val(mid)<=eps为止)因为多项式函数必然可导,并且按题目要求在[l,r]上先增后减,故其导数存在于[l,r]上且先正后负。