三分法是二分法的变种，他最基本的用途是求单峰函数的极值点。

  • 三分适用的情况：有唯一的最大值，满足最大值左侧严格单调递增，右侧严格单调递减（或左减右增）。强调严格单调，这样在确定最值是才能判断最值的位置，否则三分法不能缩小左右边界。

三分整数模板

整数的三分可能具有不确定性，可以通过改变while循环的条件while(l+3<r)来缩小范围，再通过小范围暴力更新答案

  • 对于边界的暴力不仅省去了处理边界，甚至常数也有提升，原因未知

凹函数的极小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int sfmin(){
	int l=0,r=1e9;
	while(l+2<r){
		//cerr<<l<<" "<<r<<endl;
		int m1=(r-l)/3+l;
		int m2=r-(r-l)/3;
		if(cal(m1)>cal(m2))l=m1;
		else r=m2;
	}
	int ans=cal(l);
	
	for(int i=l+1;i<=r;i++)ans=min(ans,cal(i));
	
	return ans;
}

凸函数的极大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
double sfmax(){
	int l=1,r=cnt-1;
	
	while(l+2<r){
		//cerr<<l<<" "<<r<<endl;
		int m1=(r-l)/3+l;
		int m2=r-(r-l)/3;
		if(cal(m1)<cal(m2))l=m1;
		else r=m2;
	}
	double ans=cal(l);
	
	for(int i=l+1;i<=r;i++)ans=max(ans,cal(i));
	
	return ans;
}

三分小数模板

凸函数的极大值

1
2
3
4
5
6
7
8
double l, r;
for(int i = 0; i < 300; i++) {//通过直接确定三分次数直接保证不会出现精度问题
    double lmid = l + (r - l) / 3;
    double rmid = r - (r - l) / 3;
    if(calc(lmid) <= calc(rmid))	l = lmid;
    else 	r = rmid;
}
printf("%.6f\n", calc(l));

凹函数的极小值

1
2
3
4
5
6
7
8
double l, r;
for(int i = 0; i < 300; i++) {
    double lmid = l + (r - l) / 3;
    double rmid = r - (r - l) / 3;
    if(calc(rmid) >= calc(lmid))	r = rmid;
    else 	l = lmid;
}
printf("%.6f\n", calc(l));

三分例题

wls的例题
https://codeforces.com/contest/1355/problem/E

思维题可以用三分暴力
https://codeforces.com/contest/939/problem/E
https://www.luogu.com.cn/problem/solution/CF939E

计算几何（待写
https://www.cnblogs.com/lfri/p/9944289.html
https://codeforces.com/contest/1059/problem/D

洛谷板子测试
https://www.luogu.com.cn/problem/P3382