前置

單峰函數有唯一的最大值，最大值左側的數值嚴格單調遞增，最大值右側的數值嚴格單調遞減。

單谷函數有唯一的最小值，最小值左側的數值嚴格單調遞減，最小值右側的數值嚴格單調遞增。

三分的本質

三分和二分一樣都是通過不斷縮小區間范圍直到找到要查的值，優化查找值的時間復雜度。二分是在單調序列中查找一個值，三分是在單峰函數或單谷函數中查找極值。

三分有兩個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上。

總結

數學很重要，P2571就需要數學，沒有數學證明是沒法用三分的，也就沒法寫出這篇實現代碼。要練習使用AI工具，缺知識的時候AI工具會派上大用場，關鍵是拆解問題規模，提出明確的問題。