参考《算法竞赛进阶指南》、AcWing题库

二分

二分法是一种随处可见却非常精妙的算法, 经常能为我们打开解答问题的突破口。 二分的基础的用法是在单调序列或单调函数中进行查找。因此当问题的答案具有单调性时, 就可以通过二分把求解转化为判定 (根据复杂度理论, 判定的难度小于求解), 这使得二分的运用范围变得很广泛。进一步地, 我们还可以扩展到通过三分法去解决单峰函数的极值以及相关问题。

据说, 只有 10%10 \% 的程序员能写对二分。二分的实现方法多种多样, 但是其细节之处确实需要仔细考虑。对于整数域上的二分, 需要注意终止边界、左右区间取舍时的开闭情况, 避免漏掉答案或造成死循环; 对于实数域上的二分, 需要注意精度问题。

整数集合上的二分

本文所使用的二分的写法保证最终答案处于闭区间 [l,r][l, r] 以内, 循环以 l=rl=r 结束, 每次二分的中间值 mid 会归属于左半段与右半段二者之一。

在单调递增序列 aa 中查找 ≥x\geq x 的数中最小的一个 (即 xx 或 xx 的后继):

1
2
3
4
5
6
while (l < r) {
	int mid = (l + r) >> 1;
	if (a[mid] >= x) r = mid;
	else l = mid + 1;
}
return a[l];

在单调递增序列 aa 中查找 ≤x\leq x 的数中最大的一个（即 xx 或 xx 的前驱）：

1
2
3
4
5
6
while (l < r) {
	int mid = (l + r + 1) >> 1;
	if (a[mid] <= x) l = mid;
	else r = mid - 1;
}
return a[l];

在第一段代码中, 若 a[mid]≥xa[\mathrm{mid}] \geq x, 则根据序列 aa 的单调性, mid 之后的数会更大, 所以 ≥x\geq x 的最小的数不可能在 mid 之后, 可行区间应该缩小为左半段。因为 mid\mathrm{mid} 也可能是答案, 故此时应取 r=r= mid。同理, 若 a[mid]<xa[\mathrm{mid}]<x, 取 l=mid+1l=m i d+1 。

在第二段代码中, 若 a[mid]≤xa[\mathrm{mid}] \leq x, 则根据序列 aa 的单调性, mid 之前的数会更小, 所以 ≤x\leq x 的最大的数不可能在 mid 之前, 可行区间应该缩小为右半段。因为 mid\mathrm{mid} 也可能是答案, 故此时应取 l=mid⁡l=\operatorname{mid} 。同理, 若 a[mid]>xa[\mathrm{mid}]>x, 取 r=mid⁡−1r=\operatorname{mid}-1 。

如上面两段代码所示, 这种二分写法可能会有两种形式:

  1. 缩小范围时, r=mid,l=mid+1r=m i d, l=m i d+1, 取中间值时, mid=(l+r)≫1m i d=(l+r) \gg 1 。
  2. 缩小范围时, l=mid,r=mid−1l=m i d, r=m i d-1, 取中间值时, mid=(l+r+1)≫1m i d=(l+r+1) \gg 1 。

如果不对 mid 的取法加以区分, 假如第二段代码也采用 mid=(l+r)≫1mid =(l+r) \gg 1, 那么当 r−lr-l 等于 1 时, 就有 mid=(l+r)≫1=lmid =(l+r) \gg 1=l 。接下来若进入 l=midl=m i d 分支, 可行区间未缩小, 造成死循环: 若进入 r=mid−1r=m i d-1 分支, 造成 l>rl>r, 循环不能以 l=rl=r 结束。因此对两个形式采用配套的 mid 取法是必要的。上面两段代码所示的两个形式共同组成了这种二分的实现方法。注意, 我们在二分实现中采用了右移运算 ≫1\gg 1 , 而不是整数除法 /2/ 2 。这是因为右移运算是向下取整, 而整数除法是向零取整, 在二分值域包含负数时后者不能正常工作。

仔细分析这两种 mid 的取法, 我们还发现: mid=(l+r)≫1mid =(l+r) \gg 1 不会取到 rr 这个值, mid=(l+r+1)≫1mid =(l+r+1) \gg 1 不会取到 ll 这个值。我们可以利用这一性质来处理无解的情况, 把最初的二分区问 [1,n][1, n] 分别扩大为 [1,n+1][1, n+1] 和 [0,n][0, n], 把 aa 数组的一个越界的下标包含进来。如果最后二分终止于扩大后的这个越界下标上, 则说明 aa 中不存在所求的数。

总而言之, 正确写出这种二分的流程是:

  1. 通过分析具体问题, 确定左右半段哪一个是可行区间, 以及 mid 归属哪一半段。
  2. 根据分析结果, 选择 “ r=mid,l=mid+1r=m i d, l=m i d+1, mid =(l+r)≫1=(l+r) \gg 1 ” 和 “ l=mid,r=mid−1,mid=(l+r+1)≫1l=m i d,r=m i d-1, m i d=(l+r+1) \gg 1 ” 两个配套形式之一。
  3. 二分终止条件是 l==rl==r, 该值就是答案所在位置。

本文使用的这种二分方法的优点是始终保持答案位于二分区间内, 二分结束条件对应的值恰好在答案所处位置, 还可以很自然地处理无解的情况, 形式优美。唯一的缺点是由两种形式共同组成, 需要认真考实际问题选译对应的形式。也有其他的二分写法, 采用 “ l=l= mid +1,r=+1, r= mid −1-1 ” 或 “ l=mid,r=midl=mid, r= mid ”来避免产生两种形式, 但也相应地造成了丟失在 mid 点上的答案、二分结束时可行区间未缩小到确切答案等问题, 需要额外加以处理, 这里就不再一一讲述。

C++ STL 中的 lower_bound 与 upper_bound 函数实现了在一个序列中二分查找某个整数 xx 的后继。

实数域上的二分

在实数域上二分较为简单, 确定好所需的精度 epse p s, 以 l+eps<rl+e p s<r 为循环条件, 每次根据在 mid 上的判定选择 r=midr= mid 或 l=midl=mid 分支之一即可。一般需要保留 kk 位小数时, 则取 eps=10−(k+2)e p s=10^{-(k+2)} 。

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

有时精度不容易确定或表示, 就干脆采用循环固定次数的二分方法, 也是一种相当不错的策略。这种方法得到的结果的精度通常比设置 eps 更高。

1
2
3
4
5
for (int i = 0; i < 100; ++i) {
	double mid = (l + r) / 2；
	if (calc(mid)) r = mid;
	else l = mid;
}

三分求单峰函数极值

有一类函数被称为单峰函数, 它们拥有唯一的极大值点, 在极大值点左侧严格单调上升, 右侧严格单调下降; 或者拥有唯一的极小值点, 在极小值点左侧严格单调下降, 在极小值点右侧严格单调上升。为了避免混淆, 我们也称后一种为单谷函数。对于单峰或单谷函数, 我们可以通过三分法求其极值。

以单峰函数 ff 为例, 我们在函数定义域 [l,r][l, r] 上任取两个点 lmidl m i d 与 rmidr m i d , 把函数分为三段。

  1. 若 f(lmid)<f(rmid)f(lmid)<f(rmid), 则 lmidlmid 与 rmidrmid 要么同时处于极大值点左侧 (单调上升函数段), 要么处于极大值点两侧。无论哪种情况下, 极大值点都在 lmidlmid 右侧, 可令 l=lmidl=l m i d 。
  2. 同理, 若 f(lmid)>f(rmid)f(lmid)>f(rmid), 则极大值点一定在 rmidrmid 左侧, 可令 r=rmidr=r m i d 。 如果我们取 lmidl m i d 与 rmidr m i d 为三等分点, 那么定义域范围每次缩小 1/31 / 3 。如果我们取 lmidlmid 与 rmidrmid 在二等分点两侧极其接近的地方, 那么定义域范围每次近似缩小 1/21 / 2 。通过 log⁡\log 级别的时间复杂度即可在指定精度下求出极值。这就是三分法。

注意, 我们在介绍单峰函数时特别强调了 “严格” 单调性。若在三分过程中遇到 f(lmid)=f(rmid)f(lmid)=f(rmid) , 当函数严格单调时, 令 l=lmidl=l m i d 或 r=rmidr=r m i d 均可。如果函数不严格单调, 即在函数中存在一段值相等的部分, 那么我们无法判断定义域的左右边界如何缩小, 三分法就不再适用。

二分答案转化为判定

一个宏观的最优化问题也可以抽象为函数, 其 “定义域” 是该问题下的可行方案, 对这些可行方案进行评估得到的数值构成函数的 “值域”, 最优解就是评估值最优的方案 (不妨设评分越高越优)。假设最优解的评分是 SS, 显然对于 ∀x>S\forall x>S, 都不存在一个合法的方案达到 xx 分, 否则就与 SS 的最优性矛盾; 而对于 ∀x≤S\forall x \leq S, 一定存在一个合法的方案达到或超过 xx 分, 因为最优解就满足这个条件。这样问题的值域就具有一种特殊的单调性一一在 SS 的一侧合法、在 SS 的另一侧不合法, 就像一个在 (−∞,S](-\infty, S] 上值为 1 , 在 (S,+∞)(S,+\infty) 上值为 0 的分段函数, 可通过二分找到这个分界点 SS 。借助二分, 我 们把求最优解的问题, 转化为给定一个值 midmid , 判定是否存在一个可行方案评分达到 midmid 的问题。接下来我们通过一个经典的例子理解上述概念。

二分判定经典例子

有 NN 本书排成一行，已知第 ii 本的厚度是 AiA_i 。把它们分成连续的 MM 组，使 TT 最小化，其中 TT 表示厚度之和最大的一组的厚度。

题目描述中出现了类似于 “最大值最小” 的含义, 这是答案具有单调性, 可用二分转化为判定的最常见、最典型的特征之一。如果我们以 “把书划分为 MM 组的方案” 作为定义域, “厚度之和最大的一组的厚度” 作为评分 (即值域), 需要最小化这个厚度值, 也就是评分越小越优。相应地, 假设最终答案为 SS, 因为 SS 的最优性, 如果要求每组的厚度都 <S<S, 那么这 MM 组一定不能容纳这些书, 可能需要更多的组才能把书分完, 也就意味着对于本题的限制条件不存在可行的分书方案。如果每组的厚度可以 >S>S, 那么一定存在一种分书方案使得组数不会超过 MM 。最优解就处于分书可行性的分界点 上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 把n本书分成m组，每组厚度之和<=size，是否可行
bool valid(int size) {
	int group = 1, rest = size;
	for (int i = 1; i <= n; i++) {
		if (rest >= a[i]) rest -= a[i];
		else group++, rest = size - a[i];
	}
	return group <= m;
}

int main() {
// 二分答案，判定“每组厚度之和不超过二分的值”时能否在m组内把书分完
	int l = 0, r = sum_of_Ai;
	while (l < r) {
		int mid = (l + r) / 2;
		if (valid(mid)) r = mid; 
		else l = mid + 1;
	}
	cout << l << endl;
}

102. 最佳牛围栏

农夫约翰的农场由 NN 块田地组成，每块地里都有一定数量的牛，其数量不会少于 11 头，也不会超过 20002000 头。

约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。

围起区域内至少需要包含 FF 块地，其中 FF 会在输入中给出。

在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

输入格式

第一行输入整数 NN 和 FF，数据间用空格隔开。

接下来 NN 行，每行输入一个整数，第 i+1i+1 行输入的整数代表第 ii 片区域内包含的牛的数目。

输出格式

输出一个整数，表示平均值的最大值乘以 10001000 再 向下取整 之后得到的结果。

数据范围

1≤N≤1000001 \le N \le 100000
1≤F≤N1 \le F \le N

输入样例：

1
2
3
4
5
6
7
8
9
10
11
10 6
6 
4
2
10
3
8
5
9
4
1

输出样例：

1
6500

算法分析

二分答案, 判定 “是否存在一个长度不小于 LL 的子段, 平均数不小于二分的值” 。

如果把数列中每个数都减去二分的值, 就转化为判定 “是否存在一个长度不小于 LL 的子段, 子段和非负”。下面我们着重来解决以下两个问题:

  1. 求一个子段, 它的和最大, 没有 “长度不小于 LL ” 这个限制。
    无长度限制的最大子段和问题是一个经典问题, 只需 O(n)O(n) 扫描该数列, 不断把新的数加入子段, 当子段和变成负数时, 把当前的整个子段清空。扫描过程中出现过的最大子段和即为所求。
  2. 求一个子段, 它的和最大，子段的长度不小于 LL 。
    子段和可以转化为前缀和相减的形式, 即设 sumisum_{i} 表示 A1∼AiA_{1} \sim A_{i} 的和, 则有:

max⁡i−j≥L{Aj+1+Aj+2+⋯+Ai}=max⁡L≤i≤n{sumi−min⁡0≤j≤i−L{sumj}}\max _{i-j \geq L}\left\{A_{j+1}+A_{j+2}+\cdots+A_{i}\right\}=\max _{L \leq i \leq n}\left\{sum_{i}-\min _{0 \leq j \leq i-L}\left\{sum_{j}\right\}\right\}

仔细观察上面的式子可以发现, 随着 ii 的增长, jj 的取值范围 0∼i−L0 \sim i-L 每次只会增大 1。换言之, 每次只会有一个新的取值进入 min⁡{sumj}\min \left\{s u m_{j}\right\} 的候选集合, 所以我们没有必要每次循环枚举 jj, 只需要用一个变量记录当前最小值, 每次与新的取值 sum i−L_{i-L} 取 min 就可以了。

1
2
3
4
5
6
double ans = -1e10;
double min_val = 1e10;
for (int i = L; i <= N; ++i) {
	min_val = min(min_val, sum[i - L]);
	ans = max(ans, sum[i] - min_val);
}

解决了问题 2 之后, 我们只需要看一下最大子段和是不是非负数, 就可以确定二分上下界的变化范围了。

请读者自己思考使用二分的前提: 为什么该问题的答案具有单调性? 整道题目的参考程序如下:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
double a[100001], b[100001], sum[100001];
int main() {
	int N, L;
	cin >> N >> L;
	for (int i = 1; i <= N; i++) scanf("%lf", &a[i]);
	double eps = 1e-5;
	double l = -1e6, r = 1e6;
	while (r - l > eps) {
		double mid = (l + r) / 2;
		for (int i = 1; i <= N; i++) b[i] = a[i] - mid;
		for (int i = 1; i <= N; i++)
			sum[i] = (sum[i - 1] + b[i]);
		double ans = -1e10;
		double min_val = 1e10;
		for (int i = L; i <= N; i++) {
			min_val = min(min_val, sum[i - L]);
			ans = max(ans, sum[i] - min_val);
		}
		if (ans >= 0) l = mid; else r = mid;
	}
	cout << int(r * 1000) << endl;
}

Solution

113. 特殊排序

有 NN 个元素，编号 1,2..N1,2..N，每一对元素之间的大小关系是确定的，关系具有反对称性，但不具有传递性。

注意：不存在两个元素大小相等的情况。

也就是说，元素的大小关系是 NN 个点与 N×(N−1)2\frac{N \times (N-1)}{2} 条有向边构成的任意有向图。

然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过 1000010000 次提问来获取信息，每次提问只能了解某两个元素之间的关系。

现在请你把这 NN 个元素排成一行，使得每个元素都小于右边与它相邻的元素。

你可以通过我们预设的 bool 函数 compare 来获得两个元素之间的大小关系。

例如，编号为 aa 和 bb 的两个元素，如果元素 aa 小于元素 bb，则 compare(a,b) 返回 true，否则返回 false。

将 NN 个元素排好序后，把他们的编号以数组的形式输出，如果答案不唯一，则输出任意一个均可。

数据范围

1≤N≤10001 \le N \le 1000

输入样例

1
[[0, 1, 0], [0, 0, 0], [1, 1, 0]]

输出样例

1
[3, 1, 2]

算法分析

根据数学归纳法, 假设前 k−1k-1 个元素已经按要求排成一行, 如果能确定第 kk 个元素应该放在哪一个前面, 即可解决此问题。

我们可以通过这样一种二分法确定第 kk 个元素的位置: 若第 kk 个元素比第 midm i d 个元素小, 令 r=midr=m i d, 否则令 l=mid+1l=m i d+1 。二分的初始区间可设为 [1,k][1, k], 区间中的 kk 这个值表示放在所有 k−1k-1 个元素之后。

可以证明二分一定可以找到一个合法的位置插入, 证明如下:

  1. 如果第 kk 个元素比第 midmid 个元素小。
    继续比较 kk 与 mid−1mid-1 这两个元素, 若第 kk 个元素比第 mid−1mid-1 个元素大, 则 kk 可以插在 mid−1mid -1 与 midmid 之问; 否则说明元素 kk 比元素 mid−1mid-1 小, 那就再比较 kk 与 mid−2mid-2 这两个元素, 依此类推, 直到发现第 kk 个元素比第 1 个元素小,那就放在最前边。
  2. 如果第 kk 个元素比第 midmid 个元素大, 同理。

以上只是一个证明, 我们当然不会真的去依次比较 kk 与每个元素。实际上通过二分, 我们每询问一次 ( kk 与 midmid), 就可以把区间 [l,r][l, r] 缩小一半, 因此至多 log⁡k\log k 次询问就可以确定 kk 应该放在哪里。把 NN 个元素排成一行的总询问次数不超过 Nlog⁡NN \log N 。

本题的解答过程事实上证明了：任意有向完全图（又称竞赛图）都存在 Hamilton 路径。

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
// Forward declaration of specialSort API.
// bool specialSort(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> a;
        for(int i=0;i<N;i++){
            a.push_back(i+1);
        }
        for (int i=1;i<N;i++){
            int temp = a[i]; 
            int left = 0;
            int right = i - 1;
            int mid = 0;
            while (left <= right) {
                mid = (left + right) / 2;
                if (compare(temp,a[mid])) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            for (int j = i - 1; j >= left; j--) {
                a[j + 1] = a[j];
            }
            if (left != i) {
                a[left] = temp;
            }
        }
        return a;
    }
};

Solution