三分法 是一种用于在 单峰函数 上快速寻找极值点（最大值或最小值）的算法。我们可以把它理解为“二分法”在凹凸性场景下的升级版。二分法要求数组 单调（有序），而三分法要求函数 先单调递增再单调递减（凸/峰）或 先减后增（凹/谷）。

1、核心原理（以找最小值“凹函数”为例）

假设在区间 [l, r] 上，函数值先减后增（存在一个谷底）。

  • 取两个三等分点：m1 = l + (r - l) / 3，m2 = r - (r - l) / 3。

  • 计算 f(m1) 和 f(m2)，比较它们的大小：

    • 如果 f(m1) < f(m2)，说明谷底（最小值点）不可能在 m2 的右边，因为右侧还在上升。所以将右边界收缩：r = m2。

    • 如果 f(m1) > f(m2)，说明谷底不可能在 m1 的左边，将左边界收缩：l = m1。

  • 不断缩小区间，直到 r - l 足够小（精度满足要求），此时取 l 或 r 作为极值点。

找最大值则逻辑相反：若 f(m1) < f(m2)，说明峰值在右侧，收缩左边界 l = m1；反之收缩右边界 r = m2。、

2、适用条件

  • 函数必须具有严格的单峰性（凸性或凹性），即在整个定义域内只有一个极值点。

  • 常见的适用场景：

    • 求解二次抛物线的顶点。

    • 求几何距离的最值（如到若干个点的最短距离和）。

    • 求DP 转移方程中的决策单调性最优值（如斜率优化前的朴素凸壳查找）。

注意：如果函数是“多峰”的（有多个局部极值），三分法会失效（可能陷入局部最优），此时需用模拟退火或遗传算法。

3、三等分和近似三等分以及代码实现

“三等分”和“近似三等分”的核心区别在于点的取法不同，但它们的底层数学原理完全一致——都是利用单峰函数的单调性变化来舍弃无关区间。

为了让你彻底理解，我把这两者的“取点逻辑”和“舍弃原理”分开拆解：

1. 精确三等分（实数域的标准定义）

  • 取法：在区间 [l,r]上严格取两个点，将长度均分为 3 份。

    • 左点 m1=l+r−l​

    • 右点 m2=l+2(r−l)​

  • 效果：区间被精确切为三段：[l,m1]、[m1,m2]、[m2,r]，三段长度完全相等。

  • 代码实现：P3382 三分 - 洛谷

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-6;

double f(double x, vector<double>& v) {
    double s = 0;
    for (int i = (int)v.size() - 1; i >= 0; i--) {
        s = s * x + v[i];
    }
    return s;
}

void solve() {
    int n;
    double l, r;
    cin >> n >> l >> r;
    vector<double> a(n + 1);
    for (int i = 0; i <= n; i++) {
        cin >> a[i];
    }
    while (r - l > eps) {
        double k = (r - l) / 3.0;
        double mid1 = l + k, mid2 = r - k;
        if (f(mid1, a) > f(mid2, a)) r = mid2;
        else l = mid1;
    }
    cout << fixed << setprecision(5) << l << endl;
}

2. 近似三等分（整数/离散编程中的常见写法）

  • 取法：因为代码中自变量是整数下标，除法和取整导致无法绝对均分。常见写法是：

    • m1=l+r−l（向下取整）

    • m2=r−r−l（向下取整）

  • 效果：三段长度不完全相等。例如 l=0,r=10 时，m1=3,m2=7，三段长度为 3、4、3（中间段长了一点）

  • 代码实现：P3382 三分 - 洛谷

#include<bits/stdc++.h>
using namespace std;

const double eps = 1e-6;

double f(double x, vector<double>& v) {
    double s = 0;
    for (int i = (int)v.size() - 1; i >= 0; i--) {
        s = s * x + v[i];
    }
    return s;
}

void solve() {
    int n;
    double l, r;
    cin >> n >> l >> r;
    vector<double> a(n + 1);
    for (int i = n; i >= 0; i--) {
        cin >> a[i];
    }
    while (r - l > eps) {
        double mid = l + (r - l) / 2.0;
        if (f(mid - eps, a) > f(mid, a))r = mid;
        else l = mid;
    }
    cout << fixed << setprecision(5) << l << endl;
}

3.二者总结

三等分是“理想模型”，近似三等分是“工程实现”。它们共享同一个数学灵魂——通过两个内点的函数值大小，判断极值点的方位，从而安全地丢掉一边。只要保证 m1<m2​，近似取点就永远有效。