三分

一、思路

对于所有在定义域$[L, R]$中单调性只改变一次的函数，我们确定两个三等分点$M1$和$M2$。当$M1$对应的值小于等于$M2$的值时，$L=M1$；反之，$R=M2$。这样我们不断缩短$L$与$R$的距离，当$R-L\leq eps$时，$L$与$R$都无限接近于函数图像的拐点。

二、限制

对象必须为定义域$[L, R]$中单调性只改变一次的函数，例如对于定义域中有一段斜率为$0$函数图像则不适用。

三、模板题

洛谷 P3382 【模板】三分法

如题，给出一个$N$次函数，保证在范围$[l, r]$内存在一点$x$，使得$[l, x]$上单调增，$[x, r]$上单调减。试求出$x$的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> P;

const int maxn = 100000 + 5 ;
const int INF = 0x3f3f3f3f ;
const int mod = 9901 ;
const double eps = 1e-6;

int n;
double a[25];

double fun(double x) {
	double res = 0;
	for(int i = 0; i <= n; i++)
		res = res * x + a[i];
	return res;
}

signed main() {
	double l, r, midl, midr;
	cin >> n >> l >> r;

	for(int i = 0; i <= n; i++)
		cin >> a[i];

	while(r - l > eps) {
		double d = (r - l) / 3.0;
		midl = (l + d), midr = (r - d);
		if(fun(midl) > fun(midr))
			r = midr;
		else
			l = midl;
	}
	printf("%.5lf\n", l);
	return 0;
}

四、求导二分

对于上面的模板题，我们求的$x$的斜率为$0$，那么我们只需要把此函数求导，求导后的函数满足在$[L, R]$上单调的性质，且具有二段性：一部分大于等于$0$；一部分小于等于$0$。因此求导后可以用二分求得$x$。

缺点：如果换一道题不是多项式函数的话就不能用这个求单峰了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> P;

const int maxn = 100000 + 5 ;
const int INF = 0x3f3f3f3f ;
const int mod = 9901 ;
const double eps = 1e-6;

int n;
double a[25];

double fun(double x) {
	double res = 0;
	for(int i = 0; i < n; i++) // 常数项 消失 求导完 
		res = res * x + a[i];
	return res;
}

signed main() {
	double l, r, midl, midr;
	cin >> n >> l >> r;

	for(int i = 0; i <= n; i++)
		cin >> a[i], a[i] *= (n-i);

	while(r - l > eps) {
		double mid = (r + l) / 2.0;
		if(fun(mid) > 0)
			l = mid;
		else
			r = mid;
	}
	printf("%.5lf\n", l);
	return 0;
}