学习三分法之前，你需要先学习二分法

导入

学习三分法之前，大家应该都学会了二分法，二分法就是求解一个单调函数的零点，通俗一点，就是求解单调递增或递减序列的一个值，常用于二分查找（当然，你可以使用lower_bound或者upper_bound求解）、二分答案。

三分法就是二分法的变种，每次将一个区间分成三份，用于求解单峰函数的最值？什么是单峰函数？类似二次函数，一部分单调递增，另外一部分单调递减，有且仅有一个极值点的函数。

补充一些知识：一些三分的题目可以使用求导二分、黄金分、模拟退火、微粒群优化……各种方法解决，但是三分法足够简单。

三分操作

三分操作无疑就是以下几步：

1. 确定三分的左端点右端点记作$l,r$。

2. 将这个区间等分成三分，根据数学知识可得，这两个三等分点的横坐标分别是$l+\frac{l+r}{3}$和$r-\frac{l+r}{3}$

3. 设靠近左端点三等分点的横坐标为$lmid$，靠近右端点的三等分点的横坐标为$rmid$，那么$lmid=l+\frac{l+r}{3},rmid=r-\frac{l+r}3$，如上图，$f(lmid)>f(rmid)$，说明最大值一定在$[lmid,r]$区间内，反之最大值一定在$[l,rmid]$区间内。
4. 然后调整新的左右端点分别为$lmid,r$或者是$lmid,r$，重复操作$2,3$，直到范围足够小到确定最值。

注意，当处理实数问题时，使左端点和右端点之差小于esp（一般是$10^{-7}$）为止，可避免精度问题。

代码

来源：洛谷：P3382 【模板】三分法

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;
}