二分寻找单调序列的分界点,三分寻找单峰或单谷函数的极值点。
三分模板本身并不长,真正需要判断的是目标函数为什么只会先变好、再变坏。有些题的凸性直接写在函数式里,有些题要经过代价转换才能看出来;如果导数或离散差分具有单调性,还能把三分改写成二分。
这一篇从实数三分与整数三分开始,接着整理导数二分、离散斜率以及嵌套搜索。正文不依赖配图,重点放在单峰性的证明、边界处理和目标函数的构造。
三分到底在找什么
单峰函数与单谷函数
设函数f ( x ) f(x) f ( x ) 在区间[ l , r ] [l,r] [ l , r ] 上先单调递增,经过极值点p p p 以后单调递减:
x 1 < x 2 ≤ p ⟹ f ( x 1 ) ≤ f ( x 2 ) x_1<x_2\le p\Longrightarrow f(x_1)\le f(x_2)
x 1 < x 2 ≤ p ⟹ f ( x 1 ) ≤ f ( x 2 )
p ≤ x 1 < x 2 ⟹ f ( x 1 ) ≥ f ( x 2 ) p\le x_1<x_2\Longrightarrow f(x_1)\ge f(x_2)
p ≤ x 1 < x 2 ⟹ f ( x 1 ) ≥ f ( x 2 )
这样的函数称为单峰函数,p p p 是最大值点。
如果函数先减后增,则称为单谷函数,p p p 是最小值点。凸函数通常对应单谷,凹函数通常对应单峰,但写题时不能只凭图像判断,仍然需要说明单调性为什么只改变一次。
二分在一个位置判断左右,需要这个判断本身单调;三分同时取两个位置,通过函数值的大小排除一侧区间。
两个三分点
在区间[ l , r ] [l,r] [ l , r ] 中取:
m 1 = l + r − l 3 , m 2 = r − r − l 3 m_1=l+\frac{r-l}{3},\qquad
m_2=r-\frac{r-l}{3}
m 1 = l + 3 r − l , m 2 = r − 3 r − l
显然有l < m 1 < m 2 < r l<m_1<m_2<r l < m 1 < m 2 < r 。
先考虑单谷函数,也就是寻找最小值。如果f ( m 1 ) ≤ f ( m 2 ) f(m_1)\le f(m_2) f ( m 1 ) ≤ f ( m 2 ) ,最小值不可能严格位于m 2 m_2 m 2 右侧。否则函数从m 1 m_1 m 1 走到m 2 m_2 m 2 已经没有变小,继续向右只会更大,因此可以令:
r = m 2 r=m_2
r = m 2
反过来,如果f ( m 1 ) > f ( m 2 ) f(m_1)>f(m_2) f ( m 1 ) > f ( m 2 ) ,说明函数在这段仍然下降,最小值不可能位于m 1 m_1 m 1 左侧,可以令:
l = m 1 l=m_1
l = m 1
求单峰函数最大值时,比较方向正好相反:
目标
条件
保留区间
最小值
f ( m 1 ) ≤ f ( m 2 ) f(m_1)\le f(m_2) f ( m 1 ) ≤ f ( m 2 )
[ l , m 2 ] [l,m_2] [ l , m 2 ]
最小值
f ( m 1 ) > f ( m 2 ) f(m_1)>f(m_2) f ( m 1 ) > f ( m 2 )
[ m 1 , r ] [m_1,r] [ m 1 , r ]
最大值
f ( m 1 ) ≤ f ( m 2 ) f(m_1)\le f(m_2) f ( m 1 ) ≤ f ( m 2 )
[ m 1 , r ] [m_1,r] [ m 1 , r ]
最大值
f ( m 1 ) > f ( m 2 ) f(m_1)>f(m_2) f ( m 1 ) > f ( m 2 )
[ l , m 2 ] [l,m_2] [ l , m 2 ]
三分不是根据m 1 m_1 m 1 或m 2 m_2 m 2 是否等于答案来移动,而是根据两点之间的走势排除不可能存在极值的一侧。
复杂度
每轮三分以后,候选区间至多保留原来的2 3 \frac{2}{3} 3 2 。设初始区间长度为V V V ,要求区间长度不超过ε \varepsilon ε ,迭代次数满足:
V ( 2 3 ) K ≤ ε V\left(\frac{2}{3}\right)^K\le\varepsilon
V ( 3 2 ) K ≤ ε
因此:
K = O ( log 3 / 2 V ε ) K=O\left(\log_{3/2}\frac{V}{\varepsilon}\right)
K = O ( log 3/2 ε V )
若一次计算f ( x ) f(x) f ( x ) 需要O ( T ) O(T) O ( T ) ,实数三分的总时间复杂度为:
O ( T log V ε ) O\left(T\log\frac{V}{\varepsilon}\right)
O ( T log ε V )
三分和二分都是对数级。三分每轮保留2 3 \frac{2}{3} 3 2 ,并且通常要计算两个函数值,所以常数会比二分大。
三种常用写法
实数三分
实数没有相邻位置,不能使用m i d ± 1 mid\pm1 mi d ± 1 。求单谷函数最小值时,可以固定循环次数:
1 2 3 4 5 6 for (int t = 1 ; t <= 100 ; t++) { double m1 = l + (r - l) / 3 ; double m2 = r - (r - l) / 3 ; if (calc (m1) <= calc (m2)) r = m2; else l = m1; }
循环结束以后,极值点仍然位于[ l , r ] [l,r] [ l , r ] 中。通常取:
如果题目要求极值点,输出p p p ;如果要求极值,输出 calc(p) 。
也可以写成:
1 2 3 4 5 6 7 double eps = 1e-10 ;while (r - l > eps) { double m1 = l + (r - l) / 3 ; double m2 = r - (r - l) / 3 ; if (calc (m1) <= calc (m2)) r = m2; else l = m1; }
固定循环次数不需要反复调整 eps ,也不会因为浮点数无法继续细分而陷入死循环,竞赛中通常更省心。
整数三分
整数三分最容易出现的问题是m 1 m_1 m 1 与m 2 m_2 m 2 重合。如果区间已经很短,继续三分可能不再缩小。
更稳妥的写法是先把区间缩小到常数长度,再直接枚举:
1 2 3 4 5 6 7 8 9 while (r - l > 6 ) { i64 m1 = l + (r - l) / 3 ; i64 m2 = r - (r - l) / 3 ; if (calc (m1) <= calc (m2)) r = m2; else l = m1; } i64 ans = INF; for (i64 x = l; x <= r; x++) ans = min (ans, calc (x));
最后枚举不是多余步骤。它同时解决了取整误差、平台区间以及最优点落在相邻整数之间的问题。
导数与离散差分
对于可导的凸函数f ( x ) f(x) f ( x ) ,最小值左侧通常满足f ′ ( x ) < 0 f'(x)<0 f ′ ( x ) < 0 ,右侧满足f ′ ( x ) > 0 f'(x)>0 f ′ ( x ) > 0 。如果导数的符号只改变一次,就可以二分第一个满足:
f ′ ( x ) ≥ 0 f'(x)\ge0
f ′ ( x ) ≥ 0
的位置:
1 2 3 4 5 for (int t = 1 ; t <= 100 ; t++) { double mid = (l + r) / 2 ; if (slope (mid) < 0 ) l = mid; else r = mid; }
求凹函数最大值时,方向相反。这里二分的不是f ( x ) f(x) f ( x ) ,而是导数符号形成的分界点。
整数函数没有普通导数,可以观察离散差分:
Δ f ( x ) = f ( x + 1 ) − f ( x ) \Delta f(x)=f(x+1)-f(x)
Δ f ( x ) = f ( x + 1 ) − f ( x )
对于单谷整数函数,极小值左侧有Δ f ( x ) < 0 \Delta f(x)<0 Δ f ( x ) < 0 ,右侧有Δ f ( x ) ≥ 0 \Delta f(x)\ge0 Δ f ( x ) ≥ 0 。因此可以二分第一个满足f ( x ) ≤ f ( x + 1 ) f(x)\le f(x+1) f ( x ) ≤ f ( x + 1 ) 的位置。
导数二分和三分的渐进复杂度相同,但二分每轮只保留一半区间,通常只计算一次导数或两个相邻函数值,常数更小。前提是导数或差分容易计算,而且符号变化确实单调。
嵌套搜索
三分套三分
如果目标函数包含两个连续变量,可以先固定一个变量,再优化另一个变量。
设F ( x , y ) F(x,y) F ( x , y ) 关于y y y 是单谷函数。固定x x x 以后,内层三分得到:
G ( x ) = min y F ( x , y ) G(x)=\min_y F(x,y)
G ( x ) = y min F ( x , y )
如果G ( x ) G(x) G ( x ) 关于x x x 仍然单谷,外层就可以继续三分x x x 。
两层搜索都进行K K K 轮,单次计算F ( x , y ) F(x,y) F ( x , y ) 需要O ( T ) O(T) O ( T ) ,总时间复杂度为:
O ( K 2 T ) O(K^2T)
O ( K 2 T )
嵌套以前必须分别证明两层的单谷性。固定一个变量以后能三分,并不代表优化后的外层函数一定还能三分。
二分套三分
另一种常见结构是外层二分答案,内层三分求当前答案下的最优代价。
设我们要寻找最小的X X X 。固定X X X 后,需要计算:
G ( X ) = min y F ( X , y ) G(X)=\min_y F(X,y)
G ( X ) = y min F ( X , y )
如果F ( X , y ) F(X,y) F ( X , y ) 关于y y y 单谷,就用三分计算G ( X ) G(X) G ( X ) ;如果G ( X ) ≤ K G(X)\le K G ( X ) ≤ K 关于X X X 单调,就在外层二分X X X 。
结构可以概括为:
1 2 3 4 二分答案 X 三分变量 y 计算当前代价 F(X, y) 判断最小代价是否满足限制
若外层范围长度为V V V ,内层范围长度为W W W ,一次计算代价需要O ( T ) O(T) O ( T ) ,总时间复杂度为:
O ( T log V log W ) O(T\log V\log W)
O ( T log V log W )
例题与典型应用
下面七道题依次对应实数模板、整数三分、导数二分、整数凸代价、三分套线性扫描、三分套三分以及二分套三分。
题目
搜索对象
核心判定或函数
洛谷 P3382 三分
多项式最大值点
保证先增后减
AtCoder ABC279 D Freefall
操作次数
整数单谷函数
AtCoder ARC054 B Moore 定律
等待时间
二分导数变号点
Codeforces 1355E Restorer Distance
最终高度
调整代价单谷
Codeforces 578C Weakness and Poorness
整体平移量
最大绝对子段和
洛谷 P2571 传送带
两条线段上的位置
三分套三分
洛谷 P15260 Balancing the Barns G
最小不平衡度
二分套三分
例题一:洛谷 P3382 三分
题目链接:洛谷 P3382 三分
给定一个n n n 次多项式,并保证它在区间[ l , r ] [l,r] [ l , r ] 中先增后减,求最大值点。
题目已经给出单峰性,因此直接使用实数三分。每次计算多项式时使用霍纳法:
a n x n + a n − 1 x n − 1 + ⋯ + a 0 = ( ( ( a n x + a n − 1 ) x + a n − 2 ) x + ⋯ ) + a 0 a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0
=(((a_nx+a_{n-1})x+a_{n-2})x+\cdots)+a_0
a n x n + a n − 1 x n − 1 + ⋯ + a 0 = ((( a n x + a n − 1 ) x + a n − 2 ) x + ⋯ ) + a 0
这样一次 calc(x) 只需要O ( n ) O(n) O ( n ) ,不需要反复调用幂函数。
点击展开完整代码 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 #include <bits/stdc++.h> using namespace std;using i32 = int32_t ; using i64 = int64_t ; using i128 = __int128_t ;using u32 = uint32_t ; using u64 = uint64_t ; using u128 = __uint128_t ;int n;vector<double > a; double calc (double x) { double res = a[0 ]; for (int i = 1 ; i <= n; i++) res = res * x + a[i]; return res; } int32_t main () { ios::sync_with_stdio (false ); cin.tie (nullptr ); double l, r; cin >> n >> l >> r; a.resize (n + 1 ); for (double &x : a) cin >> x; for (int t = 1 ; t <= 100 ; t++) { double m1 = l + (r - l) / 3 ; double m2 = r - (r - l) / 3 ; if (calc (m1) <= calc (m2)) l = m1; else r = m2; } cout << fixed << setprecision (10 ) << (l + r) / 2 << '\n' ; return 0 ; }
固定循环次数为K K K ,时间复杂度为O ( K n ) O(Kn) O ( K n ) ,空间复杂度为O ( n ) O(n) O ( n ) 。这里K = 100 K=100 K = 100 ,可以视为常数。
这道题只负责建立模板。真正遇到三分题时,还需要自己证明目标函数为什么单峰或单谷。
例题二:AtCoder ABC279 D Freefall
题目链接:AtCoder ABC279 D Freefall
执行一次操作需要B B B 时间,并使重力参数增加1 1 1 。执行x x x 次操作以后,总时间为:
f ( x ) = B x + A x + 1 f(x)=Bx+\frac{A}{\sqrt{x+1}}
f ( x ) = B x + x + 1 A
其中x x x 只能取非负整数。把x x x 暂时看作实数,有:
f ′ ( x ) = B − A 2 ( x + 1 ) 3 / 2 , f ′ ′ ( x ) = 3 A 4 ( x + 1 ) 5 / 2 > 0 f'(x)=B-\frac{A}{2(x+1)^{3/2}},\qquad
f''(x)=\frac{3A}{4(x+1)^{5/2}}>0
f ′ ( x ) = B − 2 ( x + 1 ) 3/2 A , f ′′ ( x ) = 4 ( x + 1 ) 5/2 3 A > 0
因此f ( x ) f(x) f ( x ) 是凸函数,在整数定义域上同样呈单谷形态。
当x ≥ A B x\ge\frac{A}{B} x ≥ B A 时:
f ( x ) > B x ≥ A = f ( 0 ) f(x)>Bx\ge A=f(0)
f ( x ) > B x ≥ A = f ( 0 )
因此只需要搜索:
0 ≤ x ≤ ⌊ A B ⌋ 0\le x\le\left\lfloor\frac{A}{B}\right\rfloor
0 ≤ x ≤ ⌊ B A ⌋
这是整数定义域,三分到区间长度不超过6 6 6 以后,必须枚举剩余位置。
点击展开完整代码 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 #include <bits/stdc++.h> using namespace std;using i32 = int32_t ; using i64 = int64_t ; using i128 = __int128_t ;using u32 = uint32_t ; using u64 = uint64_t ; using u128 = __uint128_t ;i64 a, b; long double calc (i64 x) { return (long double )b * x + (long double )a / sqrtl (x + 1 ); }int32_t main () { ios::sync_with_stdio (false ); cin.tie (nullptr ); cin >> a >> b; i64 l = 0 , r = a / b; while (r - l > 6 ) { i64 m1 = l + (r - l) / 3 ; i64 m2 = r - (r - l) / 3 ; if (calc (m1) <= calc (m2)) r = m2; else l = m1; } long double ans = calc (l); for (i64 x = l + 1 ; x <= r; x++) ans = min (ans, calc (x)); cout << fixed << setprecision (15 ) << ans << '\n' ; return 0 ; }
三分次数为O ( log A B ) O(\log\frac{A}{B}) O ( log B A ) ,每次计算函数为O ( 1 ) O(1) O ( 1 ) ,空间复杂度为O ( 1 ) O(1) O ( 1 ) 。
这道题也能通过求导估计极小值附近的位置,但整数三分更适合练习“缩小区间后枚举”的写法。
例题三:AtCoder ARC054 B Moore 定律
题目链接:AtCoder ARC054 B Moore 定律
如果等待x x x 年再开始计算,计算机速度会变成原来的2 x / 1.5 2^{x/1.5} 2 x /1.5 倍,总完成时间为:
f ( x ) = x + P 2 x / 1.5 f(x)=x+\frac{P}{2^{x/1.5}}
f ( x ) = x + 2 x /1.5 P
直接对f ( x ) f(x) f ( x ) 三分当然可以,但这道题更适合展示导数二分。
求导得到:
f ′ ( x ) = 1 − P ln 2 1.5 ⋅ 2 − x / 1.5 f'(x)=1-\frac{P\ln2}{1.5}\cdot2^{-x/1.5}
f ′ ( x ) = 1 − 1.5 P ln 2 ⋅ 2 − x /1.5
第二项随x x x 增加而减小,所以f ′ ( x ) f'(x) f ′ ( x ) 单调递增。极小值左侧f ′ ( x ) < 0 f'(x)<0 f ′ ( x ) < 0 ,右侧f ′ ( x ) ≥ 0 f'(x)\ge0 f ′ ( x ) ≥ 0 ,可以二分导数的变号位置。
由P ≤ 10 18 P\le10^{18} P ≤ 1 0 18 可知最优等待时间不会超过100 100 100 年,因此搜索区间取[ 0 , 100 ] [0,100] [ 0 , 100 ] 即可。
点击展开完整代码 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 #include <bits/stdc++.h> using namespace std;using i32 = int32_t ; using i64 = int64_t ; using i128 = __int128_t ;using u32 = uint32_t ; using u64 = uint64_t ; using u128 = __uint128_t ;double p;double calc (double x) { return x + p / pow (2.0 , x / 1.5 ); }double slope (double x) { return 1 - p * log (2.0 ) / 1.5 / pow (2.0 , x / 1.5 ); }int32_t main () { ios::sync_with_stdio (false ); cin.tie (nullptr ); cin >> p; double l = 0 , r = 100 ; for (int t = 1 ; t <= 100 ; t++) { double mid = (l + r) / 2 ; if (slope (mid) < 0 ) l = mid; else r = mid; } cout << fixed << setprecision (10 ) << calc ((l + r) / 2 ) << '\n' ; return 0 ; }
二分轮数为K K K ,时间复杂度为O ( K ) O(K) O ( K ) ,空间复杂度为O ( 1 ) O(1) O ( 1 ) 。
求导以后也可以直接解出零点,但保留二分更有代表性:只要能够判断导数符号,就不要求零点具有方便的闭式表达式。
例题四:Codeforces 1355E Restorer Distance
题目链接:Codeforces 1355E Restorer Distance
有n n n 根高度为h i h_i h i 的柱子,可以增加、删除或移动砖块,三种操作的单位代价分别为A , R , M A,R,M A , R , M 。要求把所有柱子变成相同高度,并最小化总代价。
先处理移动代价。如果先删除一块砖,再在另一根柱子上增加一块砖,代价为A + R A+R A + R ,所以真正有效的移动代价是:
M ← min ( M , A + R ) M\leftarrow\min(M,A+R)
M ← min ( M , A + R )
固定最终高度x x x ,记需要增加的砖块数量为a d d add a dd ,能够删除的砖块数量为d e l del d e l :
a d d = ∑ h i < x ( x − h i ) add=\sum_{h_i<x}(x-h_i)
a dd = h i < x ∑ ( x − h i )
d e l = ∑ h i > x ( h i − x ) del=\sum_{h_i>x}(h_i-x)
d e l = h i > x ∑ ( h i − x )
其中min ( a d d , d e l ) \min(add,del) min ( a dd , d e l ) 块砖可以直接移动,剩余部分只能单独增加或删除,因此:
c o s t ( x ) = min ( a d d , d e l ) M + ( a d d − min ( a d d , d e l ) ) A + ( d e l − min ( a d d , d e l ) ) R cost(x)
=\min(add,del)M
+(add-\min(add,del))A
+(del-\min(add,del))R
cos t ( x ) = min ( a dd , d e l ) M + ( a dd − min ( a dd , d e l )) A + ( d e l − min ( a dd , d e l )) R
随着x x x 增加,删除需求不断减少,增加需求不断增大,单位高度带来的边际代价不会下降,所以c o s t ( x ) cost(x) cos t ( x ) 是整数单谷函数。
点击展开完整代码 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 39 40 41 42 43 #include <bits/stdc++.h> using namespace std;using i32 = int32_t ; using i64 = int64_t ; using i128 = __int128_t ;using u32 = uint32_t ; using u64 = uint64_t ; using u128 = __uint128_t ;int n;i64 ca, cr, cm; vector<i64> h; i64 calc (i64 x) { i64 add = 0 , del = 0 ; for (i64 v : h) { if (v < x) add += x - v; else del += v - x; } i64 mv = min (add, del); return mv * cm + (add - mv) * ca + (del - mv) * cr; } int32_t main () { ios::sync_with_stdio (false ); cin.tie (nullptr ); cin >> n >> ca >> cr >> cm; h.resize (n); for (i64 &x : h) cin >> x; cm = min (cm, ca + cr); i64 l = *min_element (h.begin (), h.end ()); i64 r = *max_element (h.begin (), h.end ()); while (r - l > 6 ) { i64 m1 = l + (r - l) / 3 ; i64 m2 = r - (r - l) / 3 ; if (calc (m1) <= calc (m2)) r = m2; else l = m1; } i64 ans = calc (l); for (i64 x = l + 1 ; x <= r; x++) ans = min (ans, calc (x)); cout << ans << '\n' ; return 0 ; }
设高度值域为V V V ,一次 calc 需要O ( n ) O(n) O ( n ) ,总时间复杂度为O ( n log V ) O(n\log V) O ( n log V ) ,空间复杂度为O ( n ) O(n) O ( n ) 。
这道题也可以比较c o s t ( x ) cost(x) cos t ( x ) 与c o s t ( x + 1 ) cost(x+1) cos t ( x + 1 ) ,二分离散差分变号的位置。两种写法复杂度相同,差分二分的常数更小,整数三分则更接近目标函数本身。
例题五:Codeforces 578C Weakness and Poorness
题目链接:Codeforces 578C Weakness and Poorness
给定序列a 1 , a 2 , … , a n a_1,a_2,\ldots,a_n a 1 , a 2 , … , a n ,选择实数x x x ,把每个元素变成a i − x a_i-x a i − x 。一个连续子段的代价是子段和的绝对值,要求所有子段代价中的最大值尽量小。
固定子段[ l , r ] [l,r] [ l , r ] ,其和为:
∑ i = l r ( a i − x ) = ∑ i = l r a i − ( r − l + 1 ) x \sum_{i=l}^{r}(a_i-x)
=\sum_{i=l}^{r}a_i-(r-l+1)x
i = l ∑ r ( a i − x ) = i = l ∑ r a i − ( r − l + 1 ) x
这是关于x x x 的一次函数,取绝对值以后是凸函数。所有子段对应的凸函数再取最大值,仍然是凸函数,因此目标函数:
g ( x ) = max 1 ≤ l ≤ r ≤ n ∣ ∑ i = l r ( a i − x ) ∣ g(x)=\max_{1\le l\le r\le n}
\left|\sum_{i=l}^{r}(a_i-x)\right|
g ( x ) = 1 ≤ l ≤ r ≤ n max i = l ∑ r ( a i − x )
是单谷函数,可以实数三分x x x 。
问题只剩下如何在线性时间内计算g ( x ) g(x) g ( x ) 。对于变换后的数组,分别求最大子段和m x mx m x 与最小子段和m n mn mn ,那么:
g ( x ) = max ( m x , − m n ) g(x)=\max(mx,-mn)
g ( x ) = max ( m x , − mn )
两者都可以用一次线性扫描完成。
点击展开完整代码 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 39 40 41 #include <bits/stdc++.h> using namespace std;using i32 = int32_t ; using i64 = int64_t ; using i128 = __int128_t ;using u32 = uint32_t ; using u64 = uint64_t ; using u128 = __uint128_t ;int n;vector<double > a; double calc (double x) { double hi = 0 , lo = 0 , mx = 0 , mn = 0 ; for (double v : a) { v -= x; hi = max (0.0 , hi + v); lo = min (0.0 , lo + v); mx = max (mx, hi); mn = min (mn, lo); } return max (mx, -mn); } int32_t main () { ios::sync_with_stdio (false ); cin.tie (nullptr ); cin >> n; a.resize (n); for (double &x : a) cin >> x; double l = *min_element (a.begin (), a.end ()); double r = *max_element (a.begin (), a.end ()); for (int t = 1 ; t <= 100 ; t++) { double m1 = l + (r - l) / 3 ; double m2 = r - (r - l) / 3 ; if (calc (m1) <= calc (m2)) r = m2; else l = m1; } cout << fixed << setprecision (15 ) << calc ((l + r) / 2 ) << '\n' ; return 0 ; }
固定循环次数为K K K ,一次 calc 需要O ( n ) O(n) O ( n ) ,总时间复杂度为O ( K n ) O(Kn) O ( K n ) ,空间复杂度为O ( n ) O(n) O ( n ) 。
这道题的三分模板仍然只有几行,难点在于证明“所有子段绝对值函数的最大值”具有凸性,并把一次函数计算压到O ( n ) O(n) O ( n ) 。
例题六:洛谷 P2571 传送带
题目链接:洛谷 P2571 传送带
平面上有两条传送带A B AB A B 与C D CD C D 。在A B AB A B 上的速度为P P P ,在C D CD C D 上的速度为Q Q Q ,其余位置的速度为R R R ,要求从A A A 到D D D 的最短时间。
设离开第一条传送带的位置为E E E ,进入第二条传送带的位置为F F F 。总时间为:
T ( E , F ) = ∣ A E ∣ P + ∣ E F ∣ R + ∣ F D ∣ Q T(E,F)
=\frac{|AE|}{P}
+\frac{|EF|}{R}
+\frac{|FD|}{Q}
T ( E , F ) = P ∣ A E ∣ + R ∣ E F ∣ + Q ∣ F D ∣
用x ∈ [ 0 , 1 ] x\in[0,1] x ∈ [ 0 , 1 ] 表示E E E 在线段A B AB A B 上的比例位置,用y ∈ [ 0 , 1 ] y\in[0,1] y ∈ [ 0 , 1 ] 表示F F F 在线段C D CD C D 上的比例位置。
线段上的点是参数x , y x,y x , y 的线性函数,任意两点的欧氏距离都是凸函数,因此T ( x , y ) T(x,y) T ( x , y ) 是联合凸函数。固定x x x 以后,可以三分y y y 得到当前E E E 对应的最短时间;对y y y 取最小值后,所得函数关于x x x 仍然凸,所以外层继续三分x x x 。
点击展开完整代码 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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include <bits/stdc++.h> using namespace std;using i32 = int32_t ; using i64 = int64_t ; using i128 = __int128_t ;using u32 = uint32_t ; using u64 = uint64_t ; using u128 = __uint128_t ;struct Point { double x, y; }; Point a, b, c, d; double vp, vq, vr;Point get (Point p, Point q, double t) { return {p.x + (q.x - p.x) * t, p.y + (q.y - p.y) * t}; }double dis (Point p, Point q) { return hypot (p.x - q.x, p.y - q.y); }double calc (double x, double y) { Point e = get (a, b, x); Point f = get (c, d, y); return dis (a, e) / vp + dis (e, f) / vr + dis (f, d) / vq; } double best (double x) { double l = 0 , r = 1 ; for (int t = 1 ; t <= 80 ; t++) { double m1 = l + (r - l) / 3 ; double m2 = r - (r - l) / 3 ; if (calc (x, m1) <= calc (x, m2)) r = m2; else l = m1; } return calc (x, (l + r) / 2 ); } int32_t main () { ios::sync_with_stdio (false ); cin.tie (nullptr ); cin >> a.x >> a.y >> b.x >> b.y; cin >> c.x >> c.y >> d.x >> d.y; cin >> vp >> vq >> vr; double l = 0 , r = 1 ; for (int t = 1 ; t <= 80 ; t++) { double m1 = l + (r - l) / 3 ; double m2 = r - (r - l) / 3 ; if (best (m1) <= best (m2)) r = m2; else l = m1; } cout << fixed << setprecision (2 ) << best ((l + r) / 2 ) << '\n' ; return 0 ; }
每层固定循环K K K 次,总时间复杂度为O ( K 2 ) O(K^2) O ( K 2 ) ,空间复杂度为O ( 1 ) O(1) O ( 1 ) 。
这里的参数x , y x,y x , y 都取[ 0 , 1 ] [0,1] [ 0 , 1 ] ,比直接三分坐标更统一,也不会因为线段方向不同而写出额外分类。
例题七:洛谷 P15260 Balancing the Barns G
题目链接:洛谷 P15260 Balancing the Barns G
第i i i 个谷仓有a i a_i a i 捆干草和b i b_i b i 袋饲料。一次操作会同时令:
a i ← a i − 1 , b i ← b i + 1 a_i\leftarrow a_i-1,\qquad b_i\leftarrow b_i+1
a i ← a i − 1 , b i ← b i + 1
恰好执行K K K 次操作,要求最小化:
max ( a ) − min ( b ) \max(a)-\min(b)
max ( a ) − min ( b )
设当前二分的不平衡度为d d d 。如果最终令min ( b ) ≥ x \min(b)\ge x min ( b ) ≥ x ,那么还必须满足:
max ( a ) ≤ x + d \max(a)\le x+d
max ( a ) ≤ x + d
对于第i i i 个谷仓,至少需要执行:
c i ( x ) = max ( 0 , a i − x − d , x − b i ) c_i(x)=\max(0,a_i-x-d,x-b_i)
c i ( x ) = max ( 0 , a i − x − d , x − b i )
次操作。三个部分分别对应不操作、降低a i a_i a i 以及提高b i b_i b i 。它们都是关于x x x 的一次函数,取最大值以后形成凸函数,因此:
C d ( x ) = ∑ i = 1 n c i ( x ) C_d(x)=\sum_{i=1}^{n}c_i(x)
C d ( x ) = i = 1 ∑ n c i ( x )
也是单谷函数,可以在固定d d d 以后三分x x x 。
如果某个谷仓满足a i − b i > d a_i-b_i>d a i − b i > d ,那么允许x x x 取值的区间暂时为空。必须先执行:
t i = ⌈ a i − b i − d 2 ⌉ t_i=\left\lceil\frac{a_i-b_i-d}{2}\right\rceil
t i = ⌈ 2 a i − b i − d ⌉
次操作,使更新后的a i − b i ≤ d a_i-b_i\le d a i − b i ≤ d 。处理以后,令:
L i = a i − d , R i = b i L_i=a_i-d,\qquad R_i=b_i
L i = a i − d , R i = b i
此时L i ≤ R i L_i\le R_i L i ≤ R i ,而第i i i 个谷仓的额外代价就是点x x x 到区间[ L i , R i ] [L_i,R_i] [ L i , R i ] 的距离:
x x x 的位置
额外代价c i ( x ) c_i(x) c i ( x )
x < L i x<L_i x < L i
L i − x L_i-x L i − x
L i ≤ x ≤ R i L_i\le x\le R_i L i ≤ x ≤ R i
0 0 0
x > R i x>R_i x > R i
x − R i x-R_i x − R i
把所有L i L_i L i 与R i R_i R i 分别排序并维护前缀和,就能用两次二分在O ( log n ) O(\log n) O ( log n ) 内计算C d ( x ) C_d(x) C d ( x ) 。内层三分得到最少操作数,再判断它是否不超过剩余的K K K 。
随着d d d 增大,限制只会放宽,所以可行性关于d d d 单调。外层二分第一个可行的d d d ,内层三分当前d d d 下的最优x x x 。
点击展开完整代码 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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 #include <bits/stdc++.h> using namespace std;using i32 = int32_t ; using i64 = int64_t ; using i128 = __int128_t ;using u32 = uint32_t ; using u64 = uint64_t ; using u128 = __uint128_t ;int n;i64 k; vector<i64> a, b; bool check (i64 d) { i64 rem = k; vector<i64> vl (n) , vr (n) ; for (int i = 0 ; i < n; i++) { i64 x = a[i], y = b[i]; if (x - y > d) { i64 t = (x - y - d + 1 ) / 2 ; if (t > rem) return false ; x -= t; y += t; rem -= t; } vl[i] = x - d; vr[i] = y; } sort (vl.begin (), vl.end ()); sort (vr.begin (), vr.end ()); vector<i128> sl (n + 1 ) , sr (n + 1 ) ; for (int i = 1 ; i <= n; i++) { sl[i] = sl[i - 1 ] + vl[i - 1 ]; sr[i] = sr[i - 1 ] + vr[i - 1 ]; } auto calc = [&](i64 x) { int p = upper_bound (vl.begin (), vl.end (), x) - vl.begin (); int q = lower_bound (vr.begin (), vr.end (), x) - vr.begin (); i128 res = sl[n] - sl[p] - (i128)(n - p) * x; res += (i128)q * x - sr[q]; return res; }; i64 l = vl.front (), r = vr.back (); while (r - l > 6 ) { i64 m1 = l + (r - l) / 3 ; i64 m2 = r - (r - l) / 3 ; if (calc (m1) <= calc (m2)) r = m2; else l = m1; } i128 need = calc (l); for (i64 x = l + 1 ; x <= r; x++) need = min (need, calc (x)); return need <= rem; } int32_t main () { ios::sync_with_stdio (false ); cin.tie (nullptr ); int T; cin >> T; while (T--) { cin >> n >> k; a.resize (n); b.resize (n); for (i64 &x : a) cin >> x; for (i64 &x : b) cin >> x; i64 l = -2100000000000000000LL ; i64 r = 2100000000000000000LL ; i64 ans = r; while (l <= r) { i64 mid = l + ((r - l) >> 1 ); if (check (mid)) { ans = mid; r = mid - 1 ; } else l = mid + 1 ; } cout << ans << '\n' ; } return 0 ; }
外层二分进行O ( log V ) O(\log V) O ( log V ) 轮。每轮需要排序端点,并在内层三分中用二分计算代价,总时间复杂度为:
O ( log V ( n log n + log W log n ) ) O\left(\log V\left(n\log n+\log W\log n\right)\right)
O ( log V ( n log n + log W log n ) )
空间复杂度为O ( n ) O(n) O ( n ) 。
判定只要求最少操作数不超过K K K 。如果还有剩余操作,继续减少某个a i a_i a i 并增加对应的b i b_i b i 不会让不平衡度变大,因此一定能够补足到恰好K K K 次。
总结与常见问题
怎样判断一道题能否三分?
可以依次检查四件事:
搜索对象是实数、整数,还是某条线段上的比例位置?
能否快速计算一个候选位置对应的目标值?
目标函数是否只会先变好、再变坏?
如果存在嵌套,内外两层的单峰性是否都能证明?
第三点最重要。如果函数出现下降、上升、再次下降,普通三分就会错误地删除真正的最优区间。
常见错误
没有证明单峰性
“看起来像一个碗”不是证明。可以从导数、离散差分、边际代价、凸函数的和或凸函数的最大值入手,说明单调方向为什么只改变一次。
最小值与最大值方向写反
求最小值时,若f ( m 1 ) ≤ f ( m 2 ) f(m_1)\le f(m_2) f ( m 1 ) ≤ f ( m 2 ) ,应该删除右侧;求最大值时则删除左侧。写模板以前先在纸上画出趋势,通常比背四种方向可靠。
整数三分没有枚举末尾区间
整数除法可能使m 1 = m 2 m_1=m_2 m 1 = m 2 ,也可能让真实最优点落在两个候选位置之间。把区间缩小到常数长度后直接枚举,代码更稳。
精度刚好等于允许误差
题目允许10 − 6 10^{-6} 1 0 − 6 误差,不代表停止条件就应该取10 − 6 10^{-6} 1 0 − 6 。计算、函数值比较和最终输出都会产生误差,固定循环80 80 80 到100 100 100 次通常更安全。
混淆极值点与极值
循环结束后,( l + r ) / 2 (l+r)/2 ( l + r ) /2 是极值点的近似位置;题目如果要求最小代价,应该输出f ( ( l + r ) / 2 ) f((l+r)/2) f (( l + r ) /2 ) ,不能直接输出位置。
calc 内部发生溢出
整数三分中的候选位置经常接近10 18 10^{18} 1 0 18 ,它参与乘法或累计以后可能超过 i64 。只有最后答案保证放入 i64 ,不代表中间过程也安全,必要时应使用 i128 。
忽略嵌套后的总复杂度
一次三分可能只进行几十轮,但三分套三分会把轮数相乘;如果每次 calc 还要线性扫描,总复杂度可能变成O ( K 2 n ) O(K^2n) O ( K 2 n ) 。必须把每一层和单次计算一起分析。
复杂度分析
类型
单次计算
搜索次数
总时间复杂度
实数三分
O ( T ) O(T) O ( T )
K K K 轮
O ( K T ) O(KT) O ( K T )
整数三分
O ( T ) O(T) O ( T )
O ( log V ) O(\log V) O ( log V )
O ( T log V ) O(T\log V) O ( T log V )
导数二分
O ( T ) O(T) O ( T )
K K K 轮
O ( K T ) O(KT) O ( K T )
离散差分二分
O ( T ) O(T) O ( T )
O ( log V ) O(\log V) O ( log V )
O ( T log V ) O(T\log V) O ( T log V )
三分套线性扫描
O ( n ) O(n) O ( n )
K K K 轮
O ( K n ) O(Kn) O ( K n )
三分套三分
O ( T ) O(T) O ( T )
每层K K K 轮
O ( K 2 T ) O(K^2T) O ( K 2 T )
二分套三分
O ( T ) O(T) O ( T )
两层对数搜索
O ( T log V log W ) O(T\log V\log W) O ( T log V log W )