三分法

含义

三分法，顾名思义是类似于二分法的一种算法，是通过图像的单调性来确定区间最后得到答案的一种方法，一般存在于求最值问题中

三分法适用于类似：$y=ax^2+bx+c$的二次形函数上，这些函数的特点是存在一个最值且最值左右的图像存在单调性，即单峰或单谷函数

---

实现

观察图像与我们规定的三分点，可以发现我们不断取较大/小值去逼近最值，这里本来是要分讨的，但是主包懒得画图了，感兴趣的可以自己尝试证明(很EZ)

double l=0, r=1000;
while( fabs( r-l ) > eps )//不断逼近 
{
	double x1=( 2.0*l+r )/3.0;
	double x2=( l+2.0*r )/3.0;
	//划分两个三等分点 
	if( f( x1 ) < f( x2 ) ) r=x2;//判断那个更近 
	else l=x1;
}
cout<<f( l )<<"\n";//注意是函数值 

---

应用

例如题目：植物收集，暴力$O(n^2)$只有$80pts$

而当我们尝试画出本题的图像，会发现它是个单谷函数，于是就可以使用三分法优化到$O(nlog(n))$

三分法的关键在于将题目所求的答案转化为一个单峰或单谷的函数，这样就可以将一个$O(n)$降至$O(log(n))$的复杂度