二分寻找单调序列的分界点,三分寻找单峰或单谷函数的极值点。

三分模板本身并不长,真正需要判断的是目标函数为什么只会先变好、再变坏。有些题的凸性直接写在函数式里,有些题要经过代价转换才能看出来;如果导数或离散差分具有单调性,还能把三分改写成二分。

这一篇从实数三分与整数三分开始,接着整理导数二分、离散斜率以及嵌套搜索。正文不依赖配图,重点放在单峰性的证明、边界处理和目标函数的构造。

三分到底在找什么

单峰函数与单谷函数

设函数f(x)f(x)在区间[l,r][l,r]上先单调递增,经过极值点pp以后单调递减:

x1<x2≤p⟹f(x1)≤f(x2)x_1<x_2\le p\Longrightarrow f(x_1)\le f(x_2)

p≤x1<x2⟹f(x1)≥f(x2)p\le x_1<x_2\Longrightarrow f(x_1)\ge f(x_2)

这样的函数称为单峰函数,pp是最大值点。

如果函数先减后增,则称为单谷函数,pp是最小值点。凸函数通常对应单谷,凹函数通常对应单峰,但写题时不能只凭图像判断,仍然需要说明单调性为什么只改变一次。

二分在一个位置判断左右,需要这个判断本身单调;三分同时取两个位置,通过函数值的大小排除一侧区间。

两个三分点

在区间[l,r][l,r]中取:

m1=l+r−l3,m2=r−r−l3m_1=l+\frac{r-l}{3},\qquad m_2=r-\frac{r-l}{3}

显然有l<m1<m2<rl<m_1<m_2<r。

先考虑单谷函数,也就是寻找最小值。如果f(m1)≤f(m2)f(m_1)\le f(m_2),最小值不可能严格位于m2m_2右侧。否则函数从m1m_1走到m2m_2已经没有变小,继续向右只会更大,因此可以令:

r=m2r=m_2

反过来,如果f(m1)>f(m2)f(m_1)>f(m_2),说明函数在这段仍然下降,最小值不可能位于m1m_1左侧,可以令:

l=m1l=m_1

求单峰函数最大值时,比较方向正好相反:

目标 条件 保留区间
最小值 f(m1)≤f(m2)f(m_1)\le f(m_2) [l,m2][l,m_2]
最小值 f(m1)>f(m2)f(m_1)>f(m_2) [m1,r][m_1,r]
最大值 f(m1)≤f(m2)f(m_1)\le f(m_2) [m1,r][m_1,r]
最大值 f(m1)>f(m2)f(m_1)>f(m_2) [l,m2][l,m_2]

三分不是根据m1m_1或m2m_2是否等于答案来移动,而是根据两点之间的走势排除不可能存在极值的一侧。

复杂度

每轮三分以后,候选区间至多保留原来的23\frac{2}{3}。设初始区间长度为VV,要求区间长度不超过ε\varepsilon,迭代次数满足:

V(23)K≤εV\left(\frac{2}{3}\right)^K\le\varepsilon

因此:

K=O(log⁡3/2Vε)K=O\left(\log_{3/2}\frac{V}{\varepsilon}\right)

若一次计算f(x)f(x)需要O(T)O(T),实数三分的总时间复杂度为:

O(Tlog⁡Vε)O\left(T\log\frac{V}{\varepsilon}\right)

三分和二分都是对数级。三分每轮保留23\frac{2}{3},并且通常要计算两个函数值,所以常数会比二分大。

三种常用写法

实数三分

实数没有相邻位置,不能使用mid±1mid\pm1。求单谷函数最小值时,可以固定循环次数:

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]中。通常取:

1
double p = (l + r) / 2;

如果题目要求极值点,输出pp;如果要求极值,输出 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,也不会因为浮点数无法继续细分而陷入死循环,竞赛中通常更省心。

整数三分

整数三分最容易出现的问题是m1m_1与m2m_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)<0f'(x)<0,右侧满足f′(x)>0f'(x)>0。如果导数的符号只改变一次,就可以二分第一个满足:

f′(x)≥0f'(x)\ge0

的位置:

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+1)−f(x)\Delta f(x)=f(x+1)-f(x)

对于单谷整数函数,极小值左侧有Δf(x)<0\Delta f(x)<0,右侧有Δf(x)≥0\Delta f(x)\ge0。因此可以二分第一个满足f(x)≤f(x+1)f(x)\le f(x+1)的位置。

导数二分和三分的渐进复杂度相同,但二分每轮只保留一半区间,通常只计算一次导数或两个相邻函数值,常数更小。前提是导数或差分容易计算,而且符号变化确实单调。

嵌套搜索

三分套三分

如果目标函数包含两个连续变量,可以先固定一个变量,再优化另一个变量。

设F(x,y)F(x,y)关于yy是单谷函数。固定xx以后,内层三分得到:

G(x)=min⁡yF(x,y)G(x)=\min_y F(x,y)

如果G(x)G(x)关于xx仍然单谷,外层就可以继续三分xx。

两层搜索都进行KK轮,单次计算F(x,y)F(x,y)需要O(T)O(T),总时间复杂度为:

O(K2T)O(K^2T)

嵌套以前必须分别证明两层的单谷性。固定一个变量以后能三分,并不代表优化后的外层函数一定还能三分。

二分套三分

另一种常见结构是外层二分答案,内层三分求当前答案下的最优代价。

设我们要寻找最小的XX。固定XX后,需要计算:

G(X)=min⁡yF(X,y)G(X)=\min_y F(X,y)

如果F(X,y)F(X,y)关于yy单谷,就用三分计算G(X)G(X);如果G(X)≤KG(X)\le K关于XX单调,就在外层二分XX。

结构可以概括为:

1
2
3
4
二分答案 X
三分变量 y
计算当前代价 F(X, y)
判断最小代价是否满足限制

若外层范围长度为VV,内层范围长度为WW,一次计算代价需要O(T)O(T),总时间复杂度为:

O(Tlog⁡Vlog⁡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 三分

给定一个nn次多项式,并保证它在区间[l,r][l,r]中先增后减,求最大值点。

题目已经给出单峰性,因此直接使用实数三分。每次计算多项式时使用霍纳法:

anxn+an−1xn−1+⋯+a0=(((anx+an−1)x+an−2)x+⋯ )+a0a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0 =(((a_nx+a_{n-1})x+a_{n-2})x+\cdots)+a_0

这样一次 calc(x) 只需要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
/* Fufffh */
#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;
}

固定循环次数为KK,时间复杂度为O(Kn)O(Kn),空间复杂度为O(n)O(n)。这里K=100K=100,可以视为常数。

这道题只负责建立模板。真正遇到三分题时,还需要自己证明目标函数为什么单峰或单谷。

例题二:AtCoder ABC279 D Freefall

题目链接:AtCoder ABC279 D Freefall

执行一次操作需要BB时间,并使重力参数增加11。执行xx次操作以后,总时间为:

f(x)=Bx+Ax+1f(x)=Bx+\frac{A}{\sqrt{x+1}}

其中xx只能取非负整数。把xx暂时看作实数,有:

f′(x)=B−A2(x+1)3/2,f′′(x)=3A4(x+1)5/2>0f'(x)=B-\frac{A}{2(x+1)^{3/2}},\qquad f''(x)=\frac{3A}{4(x+1)^{5/2}}>0

因此f(x)f(x)是凸函数,在整数定义域上同样呈单谷形态。

当x≥ABx\ge\frac{A}{B}时:

f(x)>Bx≥A=f(0)f(x)>Bx\ge A=f(0)

因此只需要搜索:

0≤x≤⌊AB⌋0\le x\le\left\lfloor\frac{A}{B}\right\rfloor

这是整数定义域,三分到区间长度不超过66以后,必须枚举剩余位置。

点击展开完整代码
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
/* Fufffh */
#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⁡AB)O(\log\frac{A}{B}),每次计算函数为O(1)O(1),空间复杂度为O(1)O(1)。

这道题也能通过求导估计极小值附近的位置,但整数三分更适合练习“缩小区间后枚举”的写法。

例题三:AtCoder ARC054 B Moore 定律

题目链接:AtCoder ARC054 B Moore 定律

如果等待xx年再开始计算,计算机速度会变成原来的2x/1.52^{x/1.5}倍,总完成时间为:

f(x)=x+P2x/1.5f(x)=x+\frac{P}{2^{x/1.5}}

直接对f(x)f(x)三分当然可以,但这道题更适合展示导数二分。

求导得到:

f′(x)=1−Pln⁡21.5⋅2−x/1.5f'(x)=1-\frac{P\ln2}{1.5}\cdot2^{-x/1.5}

第二项随xx增加而减小,所以f′(x)f'(x)单调递增。极小值左侧f′(x)<0f'(x)<0,右侧f′(x)≥0f'(x)\ge0,可以二分导数的变号位置。

由P≤1018P\le10^{18}可知最优等待时间不会超过100100年,因此搜索区间取[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
/* Fufffh */
#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;
}

二分轮数为KK,时间复杂度为O(K)O(K),空间复杂度为O(1)O(1)。

求导以后也可以直接解出零点,但保留二分更有代表性:只要能够判断导数符号,就不要求零点具有方便的闭式表达式。

例题四:Codeforces 1355E Restorer Distance

题目链接:Codeforces 1355E Restorer Distance

有nn根高度为hih_i的柱子,可以增加、删除或移动砖块,三种操作的单位代价分别为A,R,MA,R,M。要求把所有柱子变成相同高度,并最小化总代价。

先处理移动代价。如果先删除一块砖,再在另一根柱子上增加一块砖,代价为A+RA+R,所以真正有效的移动代价是:

M←min⁡(M,A+R)M\leftarrow\min(M,A+R)

固定最终高度xx,记需要增加的砖块数量为addadd,能够删除的砖块数量为deldel:

add=∑hi<x(x−hi)add=\sum_{h_i<x}(x-h_i)

del=∑hi>x(hi−x)del=\sum_{h_i>x}(h_i-x)

其中min⁡(add,del)\min(add,del)块砖可以直接移动,剩余部分只能单独增加或删除,因此:

cost(x)=min⁡(add,del)M+(add−min⁡(add,del))A+(del−min⁡(add,del))Rcost(x) =\min(add,del)M +(add-\min(add,del))A +(del-\min(add,del))R

随着xx增加,删除需求不断减少,增加需求不断增大,单位高度带来的边际代价不会下降,所以cost(x)cost(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
/* Fufffh */
#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;
}

设高度值域为VV,一次 calc 需要O(n)O(n),总时间复杂度为O(nlog⁡V)O(n\log V),空间复杂度为O(n)O(n)。

这道题也可以比较cost(x)cost(x)与cost(x+1)cost(x+1),二分离散差分变号的位置。两种写法复杂度相同,差分二分的常数更小,整数三分则更接近目标函数本身。

例题五:Codeforces 578C Weakness and Poorness

题目链接:Codeforces 578C Weakness and Poorness

给定序列a1,a2,…,ana_1,a_2,\ldots,a_n,选择实数xx,把每个元素变成ai−xa_i-x。一个连续子段的代价是子段和的绝对值,要求所有子段代价中的最大值尽量小。

固定子段[l,r][l,r],其和为:

∑i=lr(ai−x)=∑i=lrai−(r−l+1)x\sum_{i=l}^{r}(a_i-x) =\sum_{i=l}^{r}a_i-(r-l+1)x

这是关于xx的一次函数,取绝对值以后是凸函数。所有子段对应的凸函数再取最大值,仍然是凸函数,因此目标函数:

g(x)=max⁡1≤l≤r≤n∣∑i=lr(ai−x)∣g(x)=\max_{1\le l\le r\le n} \left|\sum_{i=l}^{r}(a_i-x)\right|

是单谷函数,可以实数三分xx。

问题只剩下如何在线性时间内计算g(x)g(x)。对于变换后的数组,分别求最大子段和mxmx与最小子段和mnmn,那么:

g(x)=max⁡(mx,−mn)g(x)=\max(mx,-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
/* Fufffh */
#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;
}

固定循环次数为KK,一次 calc 需要O(n)O(n),总时间复杂度为O(Kn)O(Kn),空间复杂度为O(n)O(n)。

这道题的三分模板仍然只有几行,难点在于证明“所有子段绝对值函数的最大值”具有凸性,并把一次函数计算压到O(n)O(n)。

例题六:洛谷 P2571 传送带

题目链接:洛谷 P2571 传送带

平面上有两条传送带ABAB与CDCD。在ABAB上的速度为PP,在CDCD上的速度为QQ,其余位置的速度为RR,要求从AA到DD的最短时间。

设离开第一条传送带的位置为EE,进入第二条传送带的位置为FF。总时间为:

T(E,F)=∣AE∣P+∣EF∣R+∣FD∣QT(E,F) =\frac{|AE|}{P} +\frac{|EF|}{R} +\frac{|FD|}{Q}

用x∈[0,1]x\in[0,1]表示EE在线段ABAB上的比例位置,用y∈[0,1]y\in[0,1]表示FF在线段CDCD上的比例位置。

线段上的点是参数x,yx,y的线性函数,任意两点的欧氏距离都是凸函数,因此T(x,y)T(x,y)是联合凸函数。固定xx以后,可以三分yy得到当前EE对应的最短时间;对yy取最小值后,所得函数关于xx仍然凸,所以外层继续三分xx。

点击展开完整代码
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
/* Fufffh */
#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;
}

每层固定循环KK次,总时间复杂度为O(K2)O(K^2),空间复杂度为O(1)O(1)。

这里的参数x,yx,y都取[0,1][0,1],比直接三分坐标更统一,也不会因为线段方向不同而写出额外分类。

例题七:洛谷 P15260 Balancing the Barns G

题目链接:洛谷 P15260 Balancing the Barns G

第ii个谷仓有aia_i捆干草和bib_i袋饲料。一次操作会同时令:

ai←ai−1,bi←bi+1a_i\leftarrow a_i-1,\qquad b_i\leftarrow b_i+1

恰好执行KK次操作,要求最小化:

max⁡(a)−min⁡(b)\max(a)-\min(b)

设当前二分的不平衡度为dd。如果最终令min⁡(b)≥x\min(b)\ge x,那么还必须满足:

max⁡(a)≤x+d\max(a)\le x+d

对于第ii个谷仓,至少需要执行:

ci(x)=max⁡(0,ai−x−d,x−bi)c_i(x)=\max(0,a_i-x-d,x-b_i)

次操作。三个部分分别对应不操作、降低aia_i以及提高bib_i。它们都是关于xx的一次函数,取最大值以后形成凸函数,因此:

Cd(x)=∑i=1nci(x)C_d(x)=\sum_{i=1}^{n}c_i(x)

也是单谷函数,可以在固定dd以后三分xx。

如果某个谷仓满足ai−bi>da_i-b_i>d,那么允许xx取值的区间暂时为空。必须先执行:

ti=⌈ai−bi−d2⌉t_i=\left\lceil\frac{a_i-b_i-d}{2}\right\rceil

次操作,使更新后的ai−bi≤da_i-b_i\le d。处理以后,令:

Li=ai−d,Ri=biL_i=a_i-d,\qquad R_i=b_i

此时Li≤RiL_i\le R_i,而第ii个谷仓的额外代价就是点xx到区间[Li,Ri][L_i,R_i]的距离:

xx的位置 额外代价ci(x)c_i(x)
x<Lix<L_i Li−xL_i-x
Li≤x≤RiL_i\le x\le R_i 00
x>Rix>R_i x−Rix-R_i

把所有LiL_i与RiR_i分别排序并维护前缀和,就能用两次二分在O(log⁡n)O(\log n)内计算Cd(x)C_d(x)。内层三分得到最少操作数,再判断它是否不超过剩余的KK。

随着dd增大,限制只会放宽,所以可行性关于dd单调。外层二分第一个可行的dd,内层三分当前dd下的最优xx。

点击展开完整代码
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
/* Fufffh */
#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(nlog⁡n+log⁡Wlog⁡n))O\left(\log V\left(n\log n+\log W\log n\right)\right)

空间复杂度为O(n)O(n)。

判定只要求最少操作数不超过KK。如果还有剩余操作,继续减少某个aia_i并增加对应的bib_i不会让不平衡度变大,因此一定能够补足到恰好KK次。

总结与常见问题

怎样判断一道题能否三分?

可以依次检查四件事:

  1. 搜索对象是实数、整数,还是某条线段上的比例位置?
  2. 能否快速计算一个候选位置对应的目标值?
  3. 目标函数是否只会先变好、再变坏?
  4. 如果存在嵌套,内外两层的单峰性是否都能证明?

第三点最重要。如果函数出现下降、上升、再次下降,普通三分就会错误地删除真正的最优区间。

常见错误

没有证明单峰性

“看起来像一个碗”不是证明。可以从导数、离散差分、边际代价、凸函数的和或凸函数的最大值入手,说明单调方向为什么只改变一次。

最小值与最大值方向写反

求最小值时,若f(m1)≤f(m2)f(m_1)\le f(m_2),应该删除右侧;求最大值时则删除左侧。写模板以前先在纸上画出趋势,通常比背四种方向可靠。

整数三分没有枚举末尾区间

整数除法可能使m1=m2m_1=m_2,也可能让真实最优点落在两个候选位置之间。把区间缩小到常数长度后直接枚举,代码更稳。

精度刚好等于允许误差

题目允许10−610^{-6}误差,不代表停止条件就应该取10−610^{-6}。计算、函数值比较和最终输出都会产生误差,固定循环8080到100100次通常更安全。

混淆极值点与极值

循环结束后,(l+r)/2(l+r)/2是极值点的近似位置;题目如果要求最小代价,应该输出f((l+r)/2)f((l+r)/2),不能直接输出位置。

calc 内部发生溢出

整数三分中的候选位置经常接近101810^{18},它参与乘法或累计以后可能超过 i64。只有最后答案保证放入 i64,不代表中间过程也安全,必要时应使用 i128。

忽略嵌套后的总复杂度

一次三分可能只进行几十轮,但三分套三分会把轮数相乘;如果每次 calc 还要线性扫描,总复杂度可能变成O(K2n)O(K^2n)。必须把每一层和单次计算一起分析。

复杂度分析

类型 单次计算 搜索次数 总时间复杂度
实数三分 O(T)O(T) KK轮 O(KT)O(KT)
整数三分 O(T)O(T) O(log⁡V)O(\log V) O(Tlog⁡V)O(T\log V)
导数二分 O(T)O(T) KK轮 O(KT)O(KT)
离散差分二分 O(T)O(T) O(log⁡V)O(\log V) O(Tlog⁡V)O(T\log V)
三分套线性扫描 O(n)O(n) KK轮 O(Kn)O(Kn)
三分套三分 O(T)O(T) 每层KK轮 O(K2T)O(K^2T)
二分套三分 O(T)O(T) 两层对数搜索 O(Tlog⁡Vlog⁡W)O(T\log V\log W)