学习三分法之前，你需要先学习**二分法**
导入
学习三分法之前，大家应该都学会了二分法，二分法就是求解一个单调函数的零点，通俗一点，就是求解单调递增或递减序列的一个值，常用于二分查找（当然，你可以使用lower_bound或者upper_bound求解）、二分答案。
三分法就是二分法的变种，每次将一个区间分成三份，用于求解单峰函数的最值？什么是单峰函数？类似二次函数，一部分单调递增，另外一部分单调递减，有且仅有一个极值点的函数。
补充一些知识：一些三分的题目可以使用求导二分、黄金分、模拟退火、微粒群优化……各种方法解决，但是三分法足够简单。
三分操作
三分操作无疑就是以下几步：
-
确定三分的左端点右端点记作$l,r$。
-
将这个区间等分成三分，根据数学知识可得，这两个三等分点的横坐标分别是$l+\frac{l+r}{3}$和$r-\frac{l+r}{3}$
-
设靠近左端点三等分点的横坐标为$lmid$，靠近右端点的三等分点的横坐标为$rmid$，那么$lmid=l+\frac{l+r}{3},rmid=r-\frac{l+r}3$，如上图，$f(lmid)>f(rmid)$，说明最大值一定在$[lmid,r]$区间内，反之最大值一定在$[l,rmid]$区间内。
-
然后调整新的左右端点分别为$lmid,r$或者是$lmid,r$，重复操作$2,3$，直到范围足够小到确定最值。
注意，当处理实数问题时，使左端点和右端点之差小于esp（一般是$10^{-7}$）为止，可避免精度问题。
代码
Fast 命名空间中包括快读、快输、各种宏定义，不会影响代码阅读，您可以在左侧栏文章《代码模板》中查看具体内容。
#include<bits/stdc++.h>
using namespace std;
namespace Fast{...}
using namespace Fast;
int n;
double l,r,a[N];
double check(double x){
double zs=1,sum=0;
for(int i=n+1;i>=1;i--){
sum+=zs*a[i];
zs*=x;
}
return sum;
}
double sf(double nl,double nr){
while(nl+eps<nr){
double lmid=nl+(nr-nl)/3.0;
double rmid=nr-(nr-nl)/3.0;
if(check(lmid)<=check(rmid))
nl=lmid;
else
nr=rmid;
}
return nr;
}
int main(){
read(n);
readd(l,r);
for(int i=1;i<=n+1;i++){
readd(a[i]);
}
printd(sf(l,r),5);
return 0;
}
