二分的代码很短,难点却从来不在那几行循环里。

有时我们在有序数组中寻找一个位置,有时在答案范围中寻找可行与不可行的分界点;还有一些题,原始信息看不出任何规律,需要先转换问题,才能得到可以二分的判定函数。

这一篇从边界二分开始,接着整理二分答案、实数二分以及几种不那么直接的二分。正文不依赖配图,重点放在单调性的来源、判定函数的设计和闭区间写法的边界。

二分到底在找什么

从查找一个数到查找分界点

在一个单调不减的数组中查找xx,最直接的想法是比较amida_{mid}与xx:

  • amid<xa_{mid}<x时,答案只可能在右侧;
  • amid>xa_{mid}>x时,答案只可能在左侧;
  • amid=xa_{mid}=x时,说明找到了一个等于xx的位置。

如果数组中没有重复元素,到这里已经足够。但当xx出现多次时,“找到一个xx”和“找到第一个xx”并不是同一件事。

例如:

1
2
下标:1 2 3 4 5 6
数值:1 2 2 2 5 8

寻找第一个22,其实是在寻找第一个满足ai≥2a_i\ge 2的位置。把每个位置是否满足条件写出来:

1
2
位置:1     2    3    4    5    6
条件:false true true true true true

二分真正寻找的是 false 与 true 之间的分界点。

同理,寻找最后一个ai≤xa_i\le x的位置,会得到:

1
2
位置:1    2    3    4     5     6
条件:true true true true false false

所以二分不只是在“猜一个数”。更准确地说,它在一个有序的搜索范围中寻找边界。

两种闭区间模板

本文统一使用闭区间[l,r][l,r]。循环进行时,ll到rr之间仍然是没有排除的候选位置。

寻找第一个满足条件的位置:

1
2
3
4
5
6
7
8
9
int ans = -1;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}

当 check(mid) 成立时,midmid可能就是答案,因此先记录下来;但更靠左的位置仍然可能成立,所以继续搜索[l,mid−1][l,mid-1]。

寻找最后一个满足条件的位置:

1
2
3
4
5
6
7
8
9
int ans = -1;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}

这里的方向正好相反。条件成立以后,继续向右寻找更大的可行位置。

这种写法有两个特点:

  1. 每次都会删除midmid,因此不会在相邻位置之间死循环;
  2. 使用 ans 显式保存答案,循环结束后不需要再判断ll和rr分别指向哪里。

如果不存在满足条件的位置,ans 会保留初始值−1-1。有些题保证答案存在,也可以把它初始化成一个已知可行的边界。

mid、边界与溢出

代码中的:

1
int mid = l + r >> 1;

等价于:

1
int mid = (l + r) >> 1;

因为加法的优先级高于移位运算。只要l+rl+r不会超过类型范围,这种写法没有问题。

如果l,rl,r可能接近整数类型的上界,可以改成:

1
i64 mid = l + (r - l >> 1);

二分中的溢出不只可能发生在 mid。判定函数中的乘法、累计和以及上界计算更容易溢出。看到101810^{18}一类的数据范围时,应该从输入、答案到 check 内部全部重新检查一遍类型。

二分答案

把最优化问题改成判定问题

有些题很难直接求出最优答案,却很容易回答:

如果答案取xx,能不能完成?

设这个问题的结果为 check(x)。只要判定结果随着xx单调变化,就可以二分出可行与不可行的分界点。

最常见的两种模型如下:

模型 常见判定结果 要找的边界
最大化最小值 true ... true false ... false 最后一个 true
最小化最大值 false ... false true ... true 第一个 true

“最大化最小值”通常是把限制xx不断提高。要求越高,越难满足,因此可行答案集中在左侧。

“最小化最大值”通常是给出一个允许上限xx。上限越大,越容易满足,因此可行答案集中在右侧。

名字只能帮助我们识别模型,最终仍然要证明 check(x) 的单调方向。不能看到“最大值”或“最小值”就直接套模板。

check 函数从哪里来

设计 check 时,先暂时忘记“怎样求最优”,只考虑“给定xx以后怎样验证”。

常见的判定方式有:

  • 直接计算:算出制造xx件物品的费用,判断是否超过预算;
  • 累计贡献:把每一段能够提供的贡献相加,判断是否达到目标;
  • 贪心:固定最短距离后,尽量保留或删除某些位置;
  • 排序:固定最大值后,把限制转换成截止时间,再检查能否安排;
  • 贡献转换:把平均值至少为xx改写成若干项贡献和不小于00。

一个好的 check 只回答可行或不可行,不负责在内部重新求一次最优解。

搜索范围与复杂度

二分以前必须确定答案范围[l,r][l,r]:

  • ll应该不大于真实答案;
  • rr应该不小于真实答案;
  • 如果题目允许无解,还要准备一个不会与合法答案混淆的初始值。

上界可以来自题目数据,也可以由一个显然可行的方案推出。例如nn个任务每秒完成一个,那么最后一个任务最多等待n−1n-1秒,据此就能估计最大代价。

如果答案没有明显上界,但能够保证 check(x) 最终成立,可以先倍增找到一个可行上界:

1
2
i64 r = 1;
while (!check(r)) r <<= 1;

若答案为AA,倍增只需要O(log⁡A)O(\log A)次判定。实际使用时仍要结合数据范围限制rr,避免左移溢出;如果题目可能无解,也不能无限倍增。

如果一次 check 的时间复杂度为O(T)O(T),答案范围长度为VV,总时间复杂度为:

O(Tlog⁡V)O(T\log V)

log⁡V\log V通常不大,但 check 可能包含排序、贪心甚至另一层数据结构。分析复杂度时不能只写“二分是O(log⁡V)O(\log V)”。

实数二分与更一般的二分

实数二分

整数之间存在相邻关系,实数之间没有。因此实数二分不能使用l≤rl\le r和mid±1mid\pm1。

一种写法是当区间长度不超过 eps 时结束。下面假设 check(mid) 成立时继续向右,寻找最大的可行值:

1
2
3
4
5
6
double eps = 1e-10;
while (r - l > eps) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}

这种写法直观,循环次数约为:

O(log⁡2r−lε)O\left(\log_2\frac{r-l}{\varepsilon}\right)

eps 应该比题目允许的误差更小。例如答案允许10−610^{-6}误差,可以取10−910^{-9}或10−1010^{-10},不要刚好取10−610^{-6}。

另一种写法是固定循环次数:

1
2
3
4
5
for (int t = 1; t <= 100; t++) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}

循环100100次以后,区间长度会缩小到原来的2−1002^{-100},已经远小于常见误差要求。它不需要反复调整 eps,也不会因为浮点精度使 mid 与某个端点重合而陷入死循环,所以竞赛中通常更稳定。

两种写法都正确。前者便于理解精度,后者更省心;如果寻找最小可行值,只需要把更新方向反过来。实数二分仍然需要单调性,输出保留六位小数也不代表计算精度只需要10−610^{-6}。

二分的对象不一定是最终答案

假设有一个二元函数f(a,b)f(a,b)。整个函数未必方便直接二分,但固定aa以后,如果f(a,b)f(a,b)关于bb单调,就可以枚举aa并二分bb。

这里二分的是“在当前aa下,第一个使f(a,b)f(a,b)达到限制的bb”,最终答案还需要在所有aa的候选结果中取最优。

所以判断能否二分时,不必只盯着最终答案。数组下标、时间、长度、某个变量,甚至一个不断扩大的集合,都可能成为搜索对象。

单调性也可以主动构造

有些题的原始返回值会上下波动,看起来无法二分。但我们真正需要的只是一个布尔判定:

false,…,false,true,…,true\mathrm{false},\ldots,\mathrm{false},\mathrm{true},\ldots,\mathrm{true}

如果能够通过奇偶性、前缀、补集或者数学变换,把原始信息转换成这样的判定结果,仍然可以二分。

后面的 Codeforces 2219B2 就属于这种情况。查询答案本身不单调,但“当前前缀是否已经包含三个目标位置”是单调的。

例题与典型应用

下面七道题分别对应边界查找、整数二分、贪心判定、二元函数、排序判定、实数二分和构造单调性。

题目 二分对象 判定或比较方式
洛谷 P2249 查找 第一个合法下标 amid≥xa_{mid}\ge x
Codeforces 1613C Poisoned Dagger 最小毒药持续时间 累计伤害是否达到hh
洛谷 P2678 跳石头 最大的最短距离 贪心移除数量是否不超过MM
AtCoder ABC246 D 2-variable Function 固定aa后的最小bb f(a,b)≥Nf(a,b)\ge N
AtCoder ABC023 D 射击王 最小的最大高度 截止时间能否全部满足
AtCoder ABC034 D 食盐水 最大可行浓度 最大的KK项贡献和是否非负
Codeforces 2219B2 Unique Values 三个目标位置 奇偶性是否不同

例题一:洛谷 P2249 查找

题目链接:洛谷 P2249 查找

给定一个单调不减的数组,每次询问数字xx第一次出现的位置;如果不存在,输出−1-1。

把条件写成ai≥xa_i\ge x,二分第一个满足条件的位置。找到边界以后,再判断该位置是否真的等于xx。

为什么不直接把条件写成ai=xa_i=x?因为相等位置的左侧和右侧可能都存在不相等的位置,判定结果不是一个连续的 false/true 区间。而ai≥xa_i\ge 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
/* 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;

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, m;
cin >> n >> m;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) {
int x, l = 1, r = n, p = -1;
cin >> x;
while (l <= r) {
int mid = l + r >> 1;
if (a[mid] >= x) {
p = mid;
r = mid - 1;
}
else l = mid + 1;
}
if (p == -1 || a[p] != x) p = -1;
cout << p << " \n"[i == m];
}
return 0;
}

每次询问的时间复杂度为O(log⁡n)O(\log n),空间复杂度为O(n)O(n)。

例题二:Codeforces 1613C Poisoned Dagger

题目链接:Codeforces 1613C Poisoned Dagger

在a1,a2,…,ana_1,a_2,\ldots,a_n时刻发动攻击。每次攻击施加持续kk秒的毒素;如果上一轮毒素尚未结束,新攻击会直接刷新持续时间。求造成至少hh点伤害所需的最小kk。

相邻两次攻击之间的间隔为ai+1−aia_{i+1}-a_i。第ii次攻击在下一次刷新以前最多造成:

min⁡(k,ai+1−ai)\min(k,a_{i+1}-a_i)

最后一次攻击后面没有新的攻击,一定可以贡献kk。因此总伤害为:

damage(k)=k+∑i=1n−1min⁡(k,ai+1−ai)damage(k)=k+\sum_{i=1}^{n-1}\min(k,a_{i+1}-a_i)

kk越大,每一项都不会减小,所以总伤害单调不减。我们要找第一个满足damage(k)≥hdamage(k)\ge h的kk。

答案不会超过hh:即使只有最后一次攻击,持续hh秒也能造成hh点伤害。因此搜索范围可以直接取[1,h][1,h]。

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

void solve() {
int n;
i64 h;
cin >> n >> h;
vector<i64> a(n);
for (i64 &x : a) cin >> x;

i64 l = 1, r = h, ans = h;
while (l <= r) {
i64 mid = l + r >> 1;
i64 sum = mid;
for (int i = 0; i + 1 < n; i++) {
sum += min(mid, a[i + 1] - a[i]);
if (sum >= h) break;
}
if (sum >= h) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << ans << '\n';
}

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int t;
cin >> t;
while (t--) solve();
return 0;
}

单次判定为O(n)O(n),总时间复杂度为O(nlog⁡h)O(n\log h),空间复杂度为O(n)O(n)。

例题三:洛谷 P2678 跳石头

题目链接:洛谷 P2678 跳石头

河道长度为LL,中间有nn块岩石,最多移走mm块。要求移除以后,相邻落脚点之间的最短距离尽可能大。

假设最短距离至少为xx。从起点开始扫描,如果当前岩石与上一块保留岩石的距离小于xx,当前岩石就不能保留;否则更新上一块保留岩石。

这种贪心始终尽量保留更靠左的岩石,为后面的跳跃留下更大的空间。扫描结束后,如果需要移除的岩石不超过mm,说明xx可行。

xx越大,需要移除的岩石只会更多,因此判定结果为:

true,…,true,false,…,false\mathrm{true},\ldots,\mathrm{true},\mathrm{false},\ldots,\mathrm{false}

我们要找最后一个可行的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
/* 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;

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int len, n, m;
cin >> len >> n >> m;
vector<int> a(n + 2);
for (int i = 1; i <= n; i++) cin >> a[i];
a[n + 1] = len;

auto check = [&](int x) {
int cnt = 0, lst = 0;
for (int i = 1; i <= n + 1; i++) {
if (a[i] - a[lst] < x) cnt++;
else lst = i;
}
return cnt <= m;
};

int l = 1, r = len, ans = 0;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
cout << ans << '\n';
return 0;
}

单次判定为O(n)O(n),总时间复杂度为O(nlog⁡L)O(n\log L),空间复杂度为O(n)O(n)。

终点不能真的被移除。代码在终点距离不足时把计数增加一次,可以理解为移除上一块保留的岩石,让终点与更早的岩石直接相连;只需要判断最少移除数量是否超过mm,计数结果仍然正确。

例题四:AtCoder ABC246 D 2-variable Function

题目链接:AtCoder ABC246 D 2-variable Function

给定NN,求不小于NN的最小整数XX,并且存在非负整数a,ba,b满足:

X=a3+a2b+ab2+b3X=a^3+a^2b+ab^2+b^3

记:

f(a,b)=a3+a2b+ab2+b3f(a,b)=a^3+a^2b+ab^2+b^3

直接二分XX并不好判断,因为“是否存在a,ba,b使f(a,b)=Xf(a,b)=X”并不单调。

换一个方向:枚举aa。当aa固定时,f(a,b)f(a,b)随着bb单调递增,可以二分第一个满足f(a,b)≥Nf(a,b)\ge N的bb,再用f(a,b)f(a,b)更新答案。

由于f(106,0)=1018f(10^6,0)=10^{18},a,ba,b只需要考虑[0,106][0,10^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
29
30
31
/* 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;

constexpr int V = 1'000'000;

i64 calc(i64 a, i64 b) { return a * a * a + a * a * b + a * b * b + b * b * b; }

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

i64 n, ans = numeric_limits<i64>::max();
cin >> n;
for (int a = 0; a <= V; a++) {
int l = 0, r = V, p = V;
while (l <= r) {
int mid = l + r >> 1;
if (calc(a, mid) >= n) {
p = mid;
r = mid - 1;
}
else l = mid + 1;
}
ans = min(ans, calc(a, p));
}
cout << ans << '\n';
return 0;
}

枚举aa需要O(V)O(V),每次二分需要O(log⁡V)O(\log V),总时间复杂度为O(Vlog⁡V)O(V\log V),空间复杂度为O(1)O(1)。

这道题还有双指针做法,但二分更直接,也更适合观察“枚举一个变量,二分另一个变量”的结构。

例题五:AtCoder ABC023 D 射击王

题目链接:AtCoder ABC023 D 射击王

第ii个气球初始高度为HiH_i,每秒上升SiS_i。从第00秒开始,每秒只能击破一个气球。得分是所有气球被击破时高度的最大值,要求最小化这个得分。

假设最大高度不能超过XX。如果X<HiX<H_i,第ii个气球在第00秒就已经超过限制,直接不可行。

否则,这个气球最晚可以在下面的时刻击破:

di=⌊X−HiSi⌋d_i=\left\lfloor\frac{X-H_i}{S_i}\right\rfloor

问题变成:每个任务需要一秒,并且有各自的截止时间did_i,能否安排完全部任务?

把截止时间从小到大排序。第ii个任务使用从00开始的时间ii,因此必须满足:

di≥id_i\ge i

XX越大,每个截止时间都不会减小,所以“能否完成”具有单调性。我们要找第一个可行的XX。

上界可以取:

max⁡1≤i≤n(Hi+Si(n−1))\max_{1\le i\le n}\left(H_i+S_i(n-1)\right)

因为任何气球最晚都能在第n−1n-1秒被击破,这个上界一定可行。

点击展开完整代码
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;

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n;
cin >> n;
vector<i64> h(n), s(n), d(n);
i64 r = 0;
for (int i = 0; i < n; i++) {
cin >> h[i] >> s[i];
r = max(r, h[i] + s[i] * (n - 1));
}

auto check = [&](i64 x) {
for (int i = 0; i < n; i++) {
if (x < h[i]) return false;
d[i] = (x - h[i]) / s[i];
}
sort(d.begin(), d.end());
for (int i = 0; i < n; i++) if (d[i] < i) return false;
return true;
};

i64 l = 0, ans = r;
while (l <= r) {
i64 mid = l + r >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << ans << '\n';
return 0;
}

单次判定需要排序,时间复杂度为O(nlog⁡n)O(n\log n)。设答案范围为VV,总时间复杂度为O(nlog⁡nlog⁡V)O(n\log n\log V),空间复杂度为O(n)O(n)。

例题六:AtCoder ABC034 D 食盐水

题目链接:AtCoder ABC034 D 食盐水

有nn瓶盐水,第ii瓶重量为wiw_i,浓度为pip_i。选择恰好kk瓶混合,求能够得到的最大浓度。

直接比较不同组合的平均浓度很麻烦。假设目标浓度为xx,第ii瓶盐水中盐的质量与目标含盐量之差为:

wipi−wix=wi(pi−x)w_i p_i-w_i x=w_i(p_i-x)

如果能够选择kk瓶,使贡献和不小于00:

∑wi(pi−x)≥0\sum w_i(p_i-x)\ge 0

就说明这kk瓶混合后的浓度至少为xx。

为了让贡献和尽可能大,每次取最大的kk项即可。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
/* 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;

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, k;
cin >> n >> k;
vector<double> w(n), p(n), a(n);
for (int i = 0; i < n; i++) cin >> w[i] >> p[i];

auto check = [&](double x) {
for (int i = 0; i < n; i++) a[i] = w[i] * (p[i] - x);
sort(a.rbegin(), a.rend());
double sum = 0;
for (int i = 0; i < k; i++) sum += a[i];
return sum >= 0;
};

double l = 0, r = 100;
for (int t = 1; t <= 100; t++) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
cout << fixed << setprecision(10) << l << '\n';
return 0;
}

设固定循环次数为TT,每次判定需要排序,总时间复杂度为O(Tnlog⁡n)O(Tn\log n),空间复杂度为O(n)O(n)。这里T=100T=100,可以视为常数。

这道题的关键不是浮点数,而是把“加权平均值至少为xx”转换成“选出的贡献和不小于00”。

例题七:Codeforces 2219B2 Unique Values

题目链接:Codeforces 2219B2 Unique Values

这是一道交互题。存在一个长度为2n+12n+1的隐藏数组,数值范围为11到nn。其中一个值出现三次,其余值均出现两次,需要找出出现三次的值所在的三个位置。

一次查询选择下标集合SS,交互器返回集合中“恰好出现一次的值”的数量,记为ask(S)ask(S)。

设某个普通值在SS中出现cc次。由于它在整个数组中只出现两次,cc只可能为0,1,20,1,2。它对集合大小和查询答案的奇偶性贡献始终相同:

cc 对∣S∣\lvert S\rvert的贡献 对ask(S)ask(S)的贡献
00 00 00
11 11 11
22 00 00

特殊值可能在SS中出现0,1,2,30,1,2,3次。前三种情况仍然相同,只有三个位置全部进入SS时,它对∣S∣\lvert S\rvert贡献奇数33,对ask(S)ask(S)却贡献00。

所以:

ask(S) mod 2≠∣S∣ mod 2ask(S)\bmod 2\ne \lvert S\rvert\bmod 2

当且仅当SS包含三个目标位置。

设目标位置从小到大为x<y<zx<y<z。

第一次令S=[1,mid]S=[1,mid]。当mid<zmid<z时,前缀没有包含全部三个位置;当mid≥zmid\ge z时,三个位置全部进入前缀,因此可以二分得到zz。

找到zz后,令:

S=[1,mid]∪{z}S=[1,mid]\cup\{z\}

并在[1,z−1][1,z-1]内二分,就能找到yy。最后固定加入y,zy,z,在[1,y−1][1,y-1]内二分得到xx。

因为2n+1≤20012n+1\le 2001:

⌈log⁡22001⌉=11\left\lceil\log_2 2001\right\rceil=11

三次二分最多使用3×11=333\times11=33次查询,正好满足限制。

点击展开原交互版本代码
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
/* 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 ask(const vector<int> &s) {
cout << "? " << s.size();
for (int x : s) cout << ' ' << x;
cout << endl;
int ans;
cin >> ans;
if (ans == -1) exit(0);
return ans;
}

int get(int r, const vector<int> &ex) {
int l = 1, ans = -1;
while (l <= r) {
int mid = l + r >> 1;
vector<int> s(mid);
iota(s.begin(), s.end(), 1);
for (int x : ex) s.push_back(x);
int res = ask(s);
if ((res & 1) ^ ((int)s.size() & 1)) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans;
}

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int z = get(2 * n + 1, {});
int y = get(z - 1, {z});
int x = get(y - 1, {y, z});
cout << "! " << x << ' ' << y << ' ' << z << endl;
}
return 0;
}

这道题的查询结果本身并不单调。真正被二分的是“当前前缀是否已经包含全部目标位置”这个经过奇偶性转换的布尔条件。

总结与常见问题

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

可以依次问三个问题:

  1. 搜索对象是什么:下标、答案、时间、长度还是某个变量?
  2. 给定一个候选值以后,能否快速判断它位于答案左侧还是右侧?
  3. 这个判断是否只会改变一次?

第三点最重要。如果判定结果出现 true、false、true 这样的反复变化,普通二分就不成立。

常见错误

没有证明单调性

“答案越大越好”不等于 check(x) 单调。必须说明xx增大以后,原来可行的方案是否仍然可行,或者原来不可行的限制是否仍然无法满足。

二分方向写反

寻找第一个 true 时,条件成立要继续向左:

1
2
ans = mid;
r = mid - 1;

寻找最后一个 true 时,条件成立要继续向右:

1
2
ans = mid;
l = mid + 1;

初始范围没有包含答案

如果rr小于真实答案,无论模板是否正确都找不到结果。答案范围应该通过数据限制或一个显然可行的方案推出,不能只凭感觉写一个很大的常数。

check 内部发生溢出

二分答案时,mid 往往还要参与乘法。例如计算制造 mid 件物品的费用,即使最终答案能够放入 i64,中间乘积也可能提前溢出。

可以在累计达到限制后提前返回,或者在确实需要时使用 i128。

把等号放错一侧

题目要求“至少达到hh”时,通常使用sum≥hsum\ge h;要求“严格小于xx”时,等号应当归入另一侧。一个等号就可能让最终答案相差11。

只分析了二分次数

二分只会调用O(log⁡V)O(\log V)次 check。如果一次判定需要O(nlog⁡n)O(n\log n),总复杂度就是O(nlog⁡nlog⁡V)O(n\log n\log V),而不是O(log⁡V)O(\log V)。

实数二分精度不足

使用 eps 时,计算精度应当严于输出误差;使用固定次数时,通常循环8080到100100次。不要让停止条件刚好等于题目允许的误差,否则浮点运算本身的误差可能影响最终结果。

复杂度分析

类型 单次判定 二分次数 总时间复杂度
有序数组边界 O(1)O(1) O(log⁡n)O(\log n) O(log⁡n)O(\log n)
整数二分答案 O(T)O(T) O(log⁡V)O(\log V) O(Tlog⁡V)O(T\log V)
实数二分 O(T)O(T) 固定KK次,或O(log⁡Vε)O\left(\log\dfrac{V}{\varepsilon}\right) O(KT)O(KT),或O(Tlog⁡Vε)O\left(T\log\dfrac{V}{\varepsilon}\right)
枚举一维、二分一维 O(1)O(1) 外层AA次、内层O(log⁡B)O(\log B) O(Alog⁡B)O(A\log B)
三次交互二分 每次一次查询 3⌈log⁡2n⌉3\lceil\log_2 n\rceil O(log⁡n)O(\log n)次查询