#创作计划# 三分
2026-04-25 15:28:19
发布于：广东
前言
三分不在 CSP 考纲内，但是还是挺有用的。
正文
作用
这时候学过一些高级货的同学就要问了：为什么不通过求导函数零点来求极值点？
客观上，求出导数后，通过二分法求出导数的零点（由于函数是单峰函数，其导数在同一范围内的零点是唯一的）得到单峰函数的极值点是可行的．
但首先，对于一些函数，求导的过程和结果比较复杂．
其次，某些题中需要求极值点的单峰函数并非一个单独的函数，而是多个函数进行特殊运算得到的函数（如求多个单调性不完全相同的一次函数的最小值的最大值）．此时函数的导函数可能是分段函数，且在函数某些点上可能不可导．
-- OI Wiki[3]
过程
我们令当前求解的区间为 ，求解要求精度至少为 。[4]
在区间内任取[5]两点 。
如果 ，则有两种可能：
- 极值点在 右侧，即在 内 的值单调递增；
- 极值点在 中。
对于这两种情况，显然极值点不可能存在于 区间内，所以可以直接令 舍去这一区间。
当 时，也是两种可能：
- 极值点在 右侧，即在 内 的值单调递减；
- 极值点在 中。
显然对于这两种情况， 区间内不可能存在极值点，我们直接令 舍去该区间。
由于三分法一般求的极值是小数，所以不用考虑等于，只需要把 拉高就行。
当 时，误差已经小到满足题目要求，可以直接输出 。
例题
P1883 【模板】三分 / 函数 / [ICPC 2010 Chengdu R] Error Curves / 无ACGO版本
题目大意
给出 个二次函数 （形如 ），定义 ，求 在 上的最小值。
思路
三分。这个 函数应该是单峰函数，不会证明但是肯定是[6]，不然这题就是模拟退火了。
三分板子，但是是单谷函数，把求解的大于和小于换换就过了，注意多测和题目要求输出的是 。
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-9;//精度
int n;
double a[101000][3];
double f(int i,double x){//求f_i(x)
return (a[i][2]*x*x + a[i][1]*x + a[i][0]);
}
double F(double x){//求F(x)
double ans = -1e9;
for(int i = 1;i <= n;i++){
ans = max(ans,f(i,x));
//cout << f(i,x) << endl;
}
//cout << '-';
//cout << f(1,x);
return ans;
}
void solve(){
memset(a,0,sizeof a);
cin >> n;
for(int i = 1;i <= n;i++){
cin >> a[i][2] >> a[i][1] >> a[i][0];
}
double l=0,r=1000;
while(r-l>eps){
double mid=(l+r)/2.0;
double lmid=mid-eps/3,rmid=mid+eps/3;//在中点进行偏移
if(F(lmid)>F(rmid))l=lmid;
else r=rmid;
}
printf("%.4lf\n",F(l));
}
int main(){
int t;cin >> t;
while(t--)solve();
}
引申——黄金分割优化法
注意到，三分每次操作都要调用两次 ，如果调用代价很高那么就容易炸掉。
那么要优化调用，我们就要使用黄金分割优化法。
首先，这是黄金分割比：
黄金分割有一个性质：
考虑一根线段 ，其中 是 靠 的黄金分割点，是靠 的黄金分割点。
那么对于线段 ， 此时就是 的靠 的黄金分割点。反之亦然。
容易想到，利用这个性质，可以取 和 为当前区间的黄金分割点，那么之后每次都可以复用一个点，降低了调用 的次数。
取黄金分割点的公式：
只需要在开始时计算这两个点对应的 值 和 。
之后在每次循环中，如果 ，就令 ， 然后再次计算一个 ；反之亦然。
全文完。
引用
也可以是单谷函数的最小值。当求单谷函数最小值时，只需要把后文中提到的求解方式里的大于改成小于小于改成大于即可。若无特殊说明，本文中只讨论单峰函数。 ↩︎
不一定是函数，只要是满足单峰/单谷性质的问题都可以这样求解。 ↩︎
https://oi-wiki.org/basic/binary/#引入“为什么不通过求导函数的零点来求极值点？” ↩︎
实际上为了减少误差，一般 会比题目要求小 ~ 个数量级，例如题目要求精度为 时一般 会设置为 左右。 ↩︎
不管取哪个点三分都能运行（在端点上除外），但是会显著影响到三分的运行速度。一般除非需要使用黄金分割优化，否则在中点偏移一个极小值的效率最高。当然，也有一些题目必须取三等分点——这种要求常见于几何题目，尤其是平面直角坐标系上。 ↩︎
其实也可能退化为一个一次函数，但是题目规定了求最小值的范围，所以没有这个问题。 ↩︎
有帮助，赞一个