三分算法

前言

在自从gdoi2016被第一题的三分虐了后，再次接触三分，其实不难。
三分算法解决凸形或者凹形函数的极值。

这里写图片描述
(令lmid=l+dfrac{r-l}{3},rmid=r-dfrac{r-l}{3})
(当lmid在函数上的值小于rmid时将l更新为lmid)；
(当rmid在函数上的值小于lmid时将r更新为rmid)；
直到(l>=r)。

(当lmid在函数上的值小于rmid时，易证lmid一定在极值的左边，所以将l更新为lmid)。
同样(当rmid在函数上的值小于lmid时，易证rmid一定在极值的右边，所以将r更新为rmid)。
通过这样来一次次缩小(l,r)的范围。

	double l=0,r=n;
	while(l+0.001<=r)
	{
		double mid1=l+(r-l)/3,mid2=r-(r-l)/3;
		if(a[mid1]<a[mid2])
			l=lmid;
		else
			r=rmid;
	}