模板及讲解

三分和二分区别

二分法用于单调函数上逼近某值，而三分法用于单峰函数 (凸函数/凹函数)上逼近极值点。

基本思路

对于区间$[l,r]$，我们求出$[l,r]$中点$mid$，再求出$[mid,r]$的中点$mmid$.

如果$f(mid) > f(mmid)$，那么$mmid$在极值点右边。
如果$f(mid) < f(mmid)$，那么$mmid$在极值点左边。

以上直接用反证法可以证明，根据单调性的定义。

然后就可以用这个方法来更新了，最后$l,r$大的那个点是极值点。

代码

例题：P3382 三分法

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define pb push_back
#define sec second
#define fir first
using namespace std;
int n;
db l, r, a[20];
const db eps = 1e-7;
db f(db x) {
    db ret = a[1];
    for (int i = 2; i <= n + 1; i++) ret = ret * x + a[i];//秦九韶算法 (提取各项的x)
    return ret;
}
void clean() {}
int solve() {
    clean();
    for (int i = 1; i <= n + 1; i++) scanf("%lf", &a[i]);
    f(2);
    db mid, mmid;
    while (fabs(r - l) > eps) {
        mid = (l + r) / 2, mmid = (mid + r) / 2;
        if (f(mid) > f(mmid)) r = mmid; else l = mid;
    }
    printf("%.5f\n", mid);
    return 0;
}
int main() {
    scanf("%d%lf%lf", &n, &l, &r), solve();
    return 0;
}

常见题型

1、三分法
Q：见讲解
解：见讲解
例题：P3382 三分法
2、三分套三分
Q：有两个点需要三分
解：有两个点需要三分，就三分后再三分一次
例题：Bzoj 1857