三分算法（曲线）

一、适用场景

        三分算法适用于求解凸性函数的极值问题，二次函数就是一个典型的单峰函数。

        二分利用的是函数的单调性，三分算法利用的是函数的单峰性。

           

        在区间[l,r]，令m1 = l + (r-l)/3, m2 = r - (r-l)/3，分别位于1/3、2/3处，接着计算这两个点的函数值，

        如果f(m1)>f(m2),求解区间有[l,r]变为[l,m2]。（就是将最接近极值点那个m点保留，然后 重新划分区间）

        此外三分算法也强调严格的单调性，出现函数值相等的区间就不适用了。

二、算法模板

double l = 0,r = 10000;
while(r-l>=0.01){//精度问题
    double m1 = l + (r-l)/3.0,m2 = r - (r-l)/3.0;
    if(f(m1)<f(m2))
        l = m1;
    else
        r = m2;
}

三、例题：https://loj.ac/problem/10013

1、ac代码：

#include<bits/stdc++.h>

using namespace std;
double a[10005],b[10005],c[10005];
int n,t;
double x,maxx = 0,L,Lmid,rmid,r;
double cal(double x)//题目中的函数计算方法
{
    int i,j;
    double maxx = -0x7fffffff;//求最大值的时候，先预设一个最小值
    for(i=1;i<=n;i++){
        maxx = max(maxx,a[i]*x*x + b[i]*x+c[i]);
    }
    return maxx;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lf%lf%lf",&a[i],&b[i],&c[i]);
        L = 0,r = 1000;
        while(L+(1e-11)<r){//三分算法寻找最小值
            Lmid = L + (r-L)/3;
            rmid = r - (r-L)/3;
            if(cal(Lmid) <= cal(rmid))
                r = rmid;
            else
                L = Lmid;
        }
        printf("%.4lf
",cal(L));
    }
    return 0;
}

 懒惰从来都是弱者的口头禅！