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

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

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

三分到底在找什么

单峰函数与单谷函数

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

$$
x_1<x_2\le p\Longrightarrow f(x_1)\le f(x_2)
$$

$$
p\le x_1<x_2\Longrightarrow f(x_1)\ge f(x_2)
$$

这样的函数称为单峰函数，$p$是最大值点。

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

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

两个三分点

在区间$[l,r]$中取：

$$
m_1=l+\frac{r-l}{3},\qquad
m_2=r-\frac{r-l}{3}
$$

显然有$l<m_1<m_2<r$。

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

$$
r=m_2
$$

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

$$
l=m_1
$$

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

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

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

复杂度

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

$$
V\left(\frac{2}{3}\right)^K\le\varepsilon
$$

因此：

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

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

$$
O\left(T\log\frac{V}{\varepsilon}\right)
$$

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

三种常用写法

实数三分

实数没有相邻位置，不能使用$mid\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]$中。通常取：

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

如果题目要求极值点，输出$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_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)<0$，右侧满足$f’(x)>0$。如果导数的符号只改变一次，就可以二分第一个满足：

$$
f’(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)$，而是导数符号形成的分界点。

整数函数没有普通导数，可以观察离散差分：

$$
\Delta f(x)=f(x+1)-f(x)
$$

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

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

嵌套搜索

三分套三分

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

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

$$
G(x)=\min_y F(x,y)
$$

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

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

$$
O(K^2T)
$$

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

二分套三分

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

设我们要寻找最小的$X$。固定$X$后，需要计算：

$$
G(X)=\min_y F(X,y)
$$

如果$F(X,y)$关于$y$单谷，就用三分计算$G(X)$；如果$G(X)\le K$关于$X$单调，就在外层二分$X$。

结构可以概括为：

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

若外层范围长度为$V$，内层范围长度为$W$，一次计算代价需要$O(T)$，总时间复杂度为：

$$
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$次多项式，并保证它在区间$[l,r]$中先增后减，求最大值点。

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

$$
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
$$

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

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

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

例题二：AtCoder ABC279 D Freefall

题目链接：AtCoder ABC279 D Freefall

执行一次操作需要$B$时间，并使重力参数增加$1$。执行$x$次操作以后，总时间为：

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

其中$x$只能取非负整数。把$x$暂时看作实数，有：

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

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

当$x\ge\frac{A}{B}$时：

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

因此只需要搜索：

$$
0\le x\le\left\lfloor\frac{A}{B}\right\rfloor
$$

这是整数定义域，三分到区间长度不超过$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
/* 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\frac{A}{B})$，每次计算函数为$O(1)$，空间复杂度为$O(1)$。

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

例题三：AtCoder ARC054 B Moore 定律

题目链接：AtCoder ARC054 B Moore 定律

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

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

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

求导得到：

$$
f’(x)=1-\frac{P\ln2}{1.5}\cdot2^{-x/1.5}
$$

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

由$P\le10^{18}$可知最优等待时间不会超过$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;
}

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

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

例题四：Codeforces 1355E Restorer Distance

题目链接：Codeforces 1355E Restorer Distance

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

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

$$
M\leftarrow\min(M,A+R)
$$

固定最终高度$x$，记需要增加的砖块数量为$add$，能够删除的砖块数量为$del$：

$$
add=\sum_{h_i<x}(x-h_i)
$$

$$
del=\sum_{h_i>x}(h_i-x)
$$

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

$$
cost(x)
=\min(add,del)M
+(add-\min(add,del))A
+(del-\min(add,del))R
$$

随着$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;
}

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

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

例题五：Codeforces 578C Weakness and Poorness

题目链接：Codeforces 578C Weakness and Poorness

给定序列$a_1,a_2,\ldots,a_n$，选择实数$x$，把每个元素变成$a_i-x$。一个连续子段的代价是子段和的绝对值，要求所有子段代价中的最大值尽量小。

固定子段$[l,r]$，其和为：

$$
\sum_{i=l}^{r}(a_i-x)
=\sum_{i=l}^{r}a_i-(r-l+1)x
$$

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

$$
g(x)=\max_{1\le l\le r\le n}
\left|\sum_{i=l}^{r}(a_i-x)\right|
$$

是单谷函数，可以实数三分$x$。

问题只剩下如何在线性时间内计算$g(x)$。对于变换后的数组，分别求最大子段和$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;
}

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

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

例题六：洛谷 P2571 传送带

题目链接：洛谷 P2571 传送带

平面上有两条传送带$AB$与$CD$。在$AB$上的速度为$P$，在$CD$上的速度为$Q$，其余位置的速度为$R$，要求从$A$到$D$的最短时间。

设离开第一条传送带的位置为$E$，进入第二条传送带的位置为$F$。总时间为：

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

用$x\in[0,1]$表示$E$在线段$AB$上的比例位置，用$y\in[0,1]$表示$F$在线段$CD$上的比例位置。

线段上的点是参数$x,y$的线性函数，任意两点的欧氏距离都是凸函数，因此$T(x,y)$是联合凸函数。固定$x$以后，可以三分$y$得到当前$E$对应的最短时间；对$y$取最小值后，所得函数关于$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
/* 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;
}

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

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

例题七：洛谷 P15260 Balancing the Barns G

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

第$i$个谷仓有$a_i$捆干草和$b_i$袋饲料。一次操作会同时令：

$$
a_i\leftarrow a_i-1,\qquad b_i\leftarrow b_i+1
$$

恰好执行$K$次操作，要求最小化：

$$
\max(a)-\min(b)
$$

设当前二分的不平衡度为$d$。如果最终令$\min(b)\ge x$，那么还必须满足：

$$
\max(a)\le x+d
$$

对于第$i$个谷仓，至少需要执行：

$$
c_i(x)=\max(0,a_i-x-d,x-b_i)
$$

次操作。三个部分分别对应不操作、降低$a_i$以及提高$b_i$。它们都是关于$x$的一次函数，取最大值以后形成凸函数，因此：

$$
C_d(x)=\sum_{i=1}^{n}c_i(x)
$$

也是单谷函数，可以在固定$d$以后三分$x$。

如果某个谷仓满足$a_i-b_i>d$，那么允许$x$取值的区间暂时为空。必须先执行：

$$
t_i=\left\lceil\frac{a_i-b_i-d}{2}\right\rceil
$$

次操作，使更新后的$a_i-b_i\le d$。处理以后，令：

$$
L_i=a_i-d,\qquad R_i=b_i
$$

此时$L_i\le R_i$，而第$i$个谷仓的额外代价就是点$x$到区间$[L_i,R_i]$的距离：

$x$的位置 额外代价$c_i(x)$
$x<L_i$ $L_i-x$
$L_i\le x\le R_i$ $0$
$x>R_i$ $x-R_i$

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

随着$d$增大，限制只会放宽，所以可行性关于$d$单调。外层二分第一个可行的$d$，内层三分当前$d$下的最优$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
/* 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\left(\log V\left(n\log n+\log W\log n\right)\right)
$$

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

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

总结与常见问题

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

可以依次检查四件事：

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

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

常见错误

没有证明单峰性

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

最小值与最大值方向写反

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

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

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

精度刚好等于允许误差

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

混淆极值点与极值

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

calc 内部发生溢出

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

忽略嵌套后的总复杂度

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

复杂度分析

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