从二分到三分——彻底掌握单峰函数求极值的“防坑”板子

三分法 (Ternary Search) 是一种用于求解单峰或单谷函数极值的算法。相比于二分查找解决单调性问题，三分法专门处理“先增后减”或“先减后增”的非单调问题。

1. 什么时候可以使用三分法？（判断条件）

在赛场上，决定使用三分法需要满足以下两个严格条件，缺一不可：

  • 目标： 题目要求寻找某个连续变量或离散变量的最优解（最大值或最小值）。
  • 性质（极度重要）： 目标函数 $f(x)$ 必须是凸函数或凹函数。即在极值点的一侧递增，另一侧递减。

赛场常见题型特征：

  1. 距离/时间物理模型： 多个物体不同方向匀速运动，求某时刻它们之间的最小距离（距离随时间先缩短后拉长，为单谷）。
  2. 成本权衡问题： 两种成本此消彼长。例如：速度越快时间成本越低，但能耗成本呈指数上升，求总成本最低的速度（U型代价函数）。
  3. 分段凸函数求和： 多个独立的凸函数代价相加，求总代价的极值（如区间调整问题）。

2. 经典赛题解析：区间端点调整代价

为了更直观地理解三分法在 ICPC 中的应用，我们来看一道非常经典的例题。

【题目大意】

给定 $n$ 个区间，将某个区间的一个端点从 $x$ 改成 $x’$ 的代价是 $(x - x’)^2$。求用最小的代价调整区间，使得调整后所有区间两两相交，且区间端点仍是整数。

数据范围：$n \le 2 \times 10^5$，值域 $0 \le V \le 10^6$。

【核心破局点：数学转化】

  1. 交点转化： 在一维坐标轴上，多个区间“两两相交”在数学上等价于“所有区间存在至少一个公共点”（这是 Helly 定理的一维推论）。所以，题目可以转化为：寻找一个目标整点 $X$，把所有够不着 $X$ 的区间强行拉长，使其包含 $X$。
  2. 代价函数构建： 对于任意单个区间 $[L_i, R_i]$，让它包含点 $X$ 的代价函数 $cost_i(X)$ 是分段的：
    • 如果 $L_i \le X \le R_i$，说明已经包含了，代价为 $0$。
    • 如果 $X < L_i$，需要把左端点 $L_i$ 往左拉到 $X$，代价是 $(L_i - X)^2$。
    • 如果 $X > R_i$，需要把右端点 $R_i$ 往右拉到 $X$，代价是 $(X - R_i)^2$。

【为什么用三分？】

仔细观察单个区间的代价函数，二次函数 $(x-a)^2$ 是一个标准的凸函数（抛物线）。而底部代价为 $0$ 的平坦段并不改变其整体的下凸性质。

在数学中有一个重要定理：凸函数相加依然是凸函数。

因此，总代价函数 $F(X) = \sum_{i=1}^{n} cost_i(X)$ 是一个巨大的单谷函数。

我们只需要在值域 $V \in [0, 10^6]$ 上对目标点 $X$ 进行整数三分。每次三分选定一个 $X$ 时，用 $O(n)$ 的时间遍历所有区间算出总代价。总时间复杂度为 $O(n \log V)$，完美通过 $2 \times 10^5$ 的数据规模。

3. 实战模板（防死循环/防精度丢失）

网上常见的标准模板在实战中容易遇到两个致命陷阱：实数域的 eps 精度死循环，以及整数域的除法趋零重合。以下两套模板专门针对竞赛环境优化，无需特判边界。

3.1 实数域三分模板（定频循环法）

核心策略： 放弃 while (r - l > eps)，直接固定循环次数。循环 100 次足以将区间缩小 $3 \times 10^{17}$ 倍，可满足任何赛题的精度要求，且 100% 不会 TLE。

C++

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
#include <iostream>
using namespace std;

// 目标函数（以求最大值为例）
double calc(double x) {
    return - (x - 50.0) * (x - 50.0) + 2500.0; 
}

double ternary_search_real(double l, double r) {
    // 固定迭代 100 次，杜绝浮点数精度死循环
    for (int i = 0; i < 100; ++i) {
        double mid1 = l + (r - l) / 3.0;
        double mid2 = r - (r - l) / 3.0;
        
        // 【比较逻辑】
        // 求最大值（单峰）：值小的区间被舍弃，if (calc(mid1) < calc(mid2))
        // 求最小值（单谷）：值大的区间被舍弃，if (calc(mid1) > calc(mid2))
        if (calc(mid1) < calc(mid2)) {
            l = mid1; 
        } else {
            r = mid2;
        }
    }
    return l; // 最终 l 与 r 重合，返回 l 即可
}

3.2 整数域三分模板（大区间三分 + 小区间暴力）

核心策略： 当 $r - l \le 2$ 时，C++ 整数除法会导致 $mid_1 = mid_2$，直接陷入死循环。策略是当区间较大时正常三分，区间缩小到 3 个数以内时，直接停止三分，用 $O(1)$ 的时间暴力枚举剩余的点。

(注：前文提到的“区间端点调整代价”例题，由于要求区间端点必须是整数，完美适配此模板。)

C++

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 <iostream>
using namespace std;

// 目标函数（以求最小代价为例，对应上述例题）
long long calc(long long x) {
    long long total_cost = 0;
    // 这里写 O(n) 的遍历逻辑，计算 x 作为交点时的总代价
    return total_cost;
}

long long ternary_search_int(long long l, long long r) {
    // 区间长度大于 2 时，保证 mid1 和 mid2 不重合
    while (r - l > 2) {
        long long mid1 = l + (r - l) / 3;
        long long mid2 = r - (r - l) / 3;
        
        // 求最小值：值大的区间被舍弃
        if (calc(mid1) > calc(mid2)) {
            l = mid1;
        } else {
            r = mid2;
        }
    }
    
    // 区间内最多剩余 3 个数，直接暴力打擂台找最小值
    long long best_x = l;
    long long min_val = calc(l);
    
    for (long long i = l + 1; i <= r; ++i) {
        long long current_val = calc(i);
        if (current_val < min_val) {
            min_val = current_val;
            best_x = i;
        }
    }
    
    return best_x; 
}

4. 进阶：如何处理“平顶/高原”问题？

什么是平顶问题？

三分法的数学前提是严格单调。如果函数在某些区间内是“平的”（例如例题中，如果所有区间一开始就已经相交，那么存在一段区域代价全为 $0$），当 $mid_1$ 和 $mid_2$ 同时落在平坦区间时，$f(mid_1) == f(mid_2)$。此时算法无法判断极值在左侧、右侧还是中间，容易丢失搜索方向。

但是不用慌！ 在我们提供的 整数三分模板 中，由于我们直接将整个区间平推逼近，且最后采用了 for 循环暴力收尾，即使遇到存在局部平顶的凹凸函数，它依然能稳定地收敛并返回平顶区域内的任意一个有效极值坐标，这对于只要求求出最值的题目来说已经足够了。

极端情况解决方案

如果题目极度刁钻，函数不仅存在大面积平顶，还要求你必须找出平顶的“最左端”或“最右端”坐标，此时纯三分法将失效，应采用：

方法：“三分求极值 + 二分求边界”

  • 步骤 1： 先用标准三分法在这个函数里找到平顶的值 $MAX_VAL$（或 $MIN_VAL$）。
  • 步骤 2： 因为在到达平顶前，函数一定是严格单调的。所以我们在 $[初始左边界, 峰顶某处坐标]$ 之间，对 $f(x)$ 进行二分查找，利用单调性寻找刚好等于该极值的最靠左（或靠右）的坐标。

总结： 遇事不决先分析代价函数。只要是由二次函数、距离差值组成的求和问题，大概率是凸函数，果断掏出三分模板，用计算力碾压！