三分算法与DeepSeek辅助证明是单峰函数

前置

单峰函数有唯一的最大值，最大值左侧的数值严格单调递增，最大值右侧的数值严格单调递减。

单谷函数有唯一的最小值，最小值左侧的数值严格单调递减，最小值右侧的数值严格单调递增。

三分的本质

三分和二分一样都是通过不断缩小区间范围直到找到要查的值，优化查找值的时间复杂度。二分是在单调序列中查找一个值，三分是在单峰函数或单谷函数中查找极值。

三分有两个mid，可确定极值位置，mid1 = L + (R - L) / 3，mid2 = R - (R - L) / 3。对于单峰函数，当f(mid1) < f(mid2)时，mid1和mid2要么在极值左侧，要么在极值两侧，这两种情况极值一定在mid1右侧，L = mid1，当f(mid1) > f(mid2)时，mid1和mid2要么在极值右侧，要么在极值两侧，这两种情况极值一定在mid2左侧，R = mid2;

二分没法在单峰函数或单谷函数中查找极值，因为单峰或单谷函数没有单调性，所以需要三分。

能用三分则该问题的某部分是单峰或单谷函数。

三分求解步骤

1.问题的某部分是否具有单峰函数或单谷函数的性质。

2.实现三分

三分基础

P3382 三分 - 洛谷

已明确是单峰函数，可用三分。

代码如下：

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 15;double vct[Maxn];double func(double x, LL n) {double res = 0.0;double x_pow = 1.0;for (LL i = 0; i <= n; ++i) {res += vct[i] * x_pow;x_pow *= x;}return res;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n;double L, R, eps = 1e-7, mid;cin >> n >> L >> R;for (LL i = n; i >= 0; --i)  cin >> vct[i];while (L + eps <  R) {mid = (L + R) / 2;if (func(mid - eps, n) > func(mid + eps, n))  R = mid;else  L = mid;}cout << fixed << setprecision(5) << L;return 0;
}

注意精度，精度的处理类似实数域中的二分做法。

一般mid1取[L, R]的三分之一位置，mid2取[L, R]的三分之二位置，如此每次区间缩小到区间的三分之二，若mid1，mid2,取[L, R]的二分之一的位置的左右两侧，则区间每次缩小到区间的二分之一左右，时间复杂度接近二分。

三分套三分

P2571 [SCOI2010] 传送带 - 洛谷

两点间中的所有线直线的距离最短，所以都走直线，那么大概走法如下图，只需确定E点和F点即可。

设两点间的直线距离为dis(x, y)，走的总距离为S = dis(A, E) / P + dis(E, F) / R + dis(F, D) / Q。设E已知，则只需关心f(E) = dis(E, F) / R + dis(F, D) / Q，若f(E)是个单峰或单谷函数即可用三分查找F的最优解，此时 S = dis(A, E) / p + f(E)，若dis(A, E) / p + f(E)是个单峰或单谷函数即可用三分查找E的最优解，需要严格的数学证明，可我不会，就问了DeepSeek，它给出了如下图的详细证明。

DeepSeek证明了一定是单峰函数，则可用三分法求解。

代码如下：

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;typedef long long LL;const double eps = 1e-8;double ax, ay, bx, by, cx, cy, dx, dy, p, Q, r;double getDis(double nx, double ny, double mx, double my) {return sqrt((nx - mx) * (nx - mx) + (ny - my) * (ny - my));
}double in_ter(double ex, double ey) {double Lx = cx, Ly = cy, Rx = dx, Ry = dy;double f1x = 0.0, f1y = 0.0, f2x = 0.0, f2y = 0.0, t1 = 0.0, t2 = 0.0;while (getDis(Lx, Ly, Rx, Ry) > eps) {f1x = Lx + (Rx - Lx) / 3.0;f1y = Ly + (Ry - Ly) / 3.0;f2x = Rx - (Rx - Lx) / 3.0;f2y = Ry - (Ry - Ly) / 3.0;t1 = getDis(ex, ey, f1x, f1y) / r + getDis(f1x, f1y, dx, dy) / Q;t2 = getDis(ex, ey, f2x, f2y) / r + getDis(f2x, f2y, dx, dy) / Q;if (t1 < t2) {Rx = f2x;Ry = f2y;} else {Lx = f1x;Ly = f1y;}}return getDis(ex, ey, Lx, Ly) / r + getDis(Lx, Ly, dx, dy) / Q;
}double out_ter() {double Lx = ax, Ly = ay, Rx = bx, Ry = by;double e1x = 0.0, e1y = 0.0, e2x = 0.0, e2y = 0.0, t1 = 0.0, t2 = 0.0;while (getDis(Lx, Ly, Rx, Ry) > eps) {e1x = Lx + (Rx - Lx) / 3.0;e1y = Ly + (Ry - Ly) / 3.0;e2x = Rx - (Rx - Lx) / 3.0;e2y = Ry - (Ry - Ly) / 3.0;t1 = getDis(ax, ay, e1x, e1y) / p + in_ter(e1x, e1y);t2 = getDis(ax, ay, e2x, e2y) / p + in_ter(e2x, e2y);if (t1 < t2) {Rx = e2x;Ry = e2y;} else {Lx = e1x;Ly = e1y;}}return getDis(ax, ay, Lx, Ly) / p + in_ter(Lx, Ly);
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> ax >> ay >> bx >> by >> cx >> cy >> dx >> dy >> p >> Q >> r;if (getDis(ax, ay, bx, by) < eps) {cout << fixed << setprecision(2) << in_ter(ax, ay);} else {cout << fixed << setprecision(2) << out_ter();}return 0;
}

最后的值是double型的，虽然输入数据是整数，但用double型表示，避免转换。

f1x为Lx，Rx三分之一的位置，f1y为Ly，Ry三分之一的位置，坐标必须能对在一起，否则(f1x,f1t)不在线段AB上。