Classical
三分：
二分一般用于在具有单调性变化的关系中查找，而三分则用于在具有抛物线型变化关系中快速查找。
算法思路：
假定我们在求函数f(x)的最大值，mid为Left和Right的中点，而midmid为mid和Right的中点。当f(mid)<f(midmid)时，令Right=midmid。否则，令Left=mid。知道Left和Right相等/非常接近。
原理证明：
f(x)的特点时在对称轴左侧和右侧均具有单调性，且单调性相反。
保证答案在区间$[Left,Right]$，如果有$f(mid)<f(midmid)$，则说明mid肯定在对称轴(答案)Max的左侧，即区间可以更新为$[mid,Right]$。否则，有反证法,$f(mid)<f(midmid)$且mid在对称轴右侧，有对称轴右侧的单调性，会有$mid>midmid$的矛盾产生。相反，若$f(mid)>f(midmid)$，则midmid肯定在对称轴的右侧,区间更新为$[Left,midmid]$
模板代码：
求最大值的代码，求最小值根据相同原理更改条件即可。
int find(int min_ans,int max_ans)//返回最大值的下表
{
int left=min_ans,right=max_ans;
while(left<right)
{
int mid=left+right>>1;
int midmid=mid+right>>1;
if(f(mid)>f(midmid))
right=midmid;
else
left=mid;
}
return left;
}
其他方法：
mid和midmid的取值也可以采用left和right的两个三等分点，其他方法一样。
题目练习：
Poj 3737 UmBasketella
题目大意：
给定圆锥体的表面积S，输出圆锥的最大体积以及此时的底面半径和高
解题思路：
经过简单的证明，我们可以发现，体积V关于底面半径R先增后减，使用三分法模板求解
代码：
typedef long double LD;
LD V(LD r,LD S){
LD l=(S-pow(r,2)*M_PI)/(M_PI*r);
return M_PI*pow(r,2)*sqrt(pow(l,2)-pow(r,2))/3;
}
int main()
{
LD S;
while(cin>>S)
{
LD l=0;
LD r=sqrt(S/(2*M_PI));
const LD esp=1e-7;
while(r-l>esp)
{
LD mid=(l+r)/2;
LD midmid=(mid+r)/2;
if(V(mid,S)<V(midmid,S)){
l=mid;
}
else{
r=midmid;
}
}
LD R=V(l,S)>V(r,S)?l:r;
LD h=sqrt( pow( S/(R*M_PI)-R,2 ) -pow(R,2) );
cout<<fixed<<setprecision(2)<<V(R,S)<<endl<<h<<endl<<R<<endl;
}
return 0;
}
Zoj 3203 Light Bulb
题目大意：
求影子的最大长度。
解题思路：
可以由相似三角形得到公式(R为人到灯下的距离)： \(f(R)=\left\{ \begin{aligned} &\frac{rH}{H-h}&R<\frac{(H-h)D}{H}\\ &D-R+H-\frac{(H-h)D}{H} & R>\frac{(H-h)D}{H} \\ \end{aligned} \right.\) 直接套用三分模板求解即可
核心代码：
LD f(LD R){
// 注意分段函数
if(R>(H-h)*D/H)
return D-R+H-(D*(H-h)/R);
else
return R*h/(H-h);
}
