二分答案

二分答案并不算什么算法，只是一类常考的题型

题目的难点一般在于选择什么东西进行二分，以及检验正确性的问题。

二分答案题目的特性：

• 答案一般具有单调性
• 有如下关键字：最短的最大，最小的最大，最大的最小等。

答案具有单调性的问题，就需要我们自己具有数学分析的能力自己去分析了。同时题目需要分析左右端点值的设置。

下面我们以砍树一题为例来介绍二分答案。

暴力做法

根据题目所求，希望求得一个最小的锯片高度使得可以切够至少 $M$ 米木材。

故而考虑枚举锯片高度。从小到大枚举锯片高度。

for (int i = 1; ; i++)

那么如何验证该锯片高度是否可行？

• 针对锯片高度 $i$，然后遍历每一棵树。
• 若树高 $a_j\geq i$，则可以切得 $a_j-i$ 的木材。
• 否则无法切得木材。
• 统计切得得木材之和，判断是否大于等于 $M$，若满足则继续循环枚举锯片高度，最后若无法得到 $M$ 米木材，则输出 $i-1$ 即可。

for (int h = 1; ; h++) // 枚举锯片高度
{
    long long sum = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] > h)
            sum += a[i] - h;
    }
    if (sum < m)
    {
        cout << h - 1;
        return 0;
    }
}

时间复杂度：$O(n\times 10^9)$，其中 $10^9$ 是锯片高度的可能枚举范围。

bool check(int h)
// 检验锯片高度是 h 的时候能否得到至少 M 米木材
{
    long long sum = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] > h)
            sum += a[i] - h;
    }
    if (sum >= m) return 1;
    return 0;
}

这样做的话显然时间复杂度非常之高。

内层循环统计切得的木材之和这个循环是无法省略的，必须遍历每一个木材来求和。

能否加快锯片高度的快速枚举（优化外层循环），答案是可以的，因为锯片高度在本题满足单调性。

随着锯片高度的不断增大，我们得到的木材数量一定是越来越少的。

故而类似于二分查找的思路，每次二分一个中间数值 $mid$ 作为锯片高度来去比较。

• 若 $mid$ 作为锯片高度可以得到 $m$ 米木材，说明 $1\sim mid$ 作为锯片高度都可以得到 $m$ 米木材，且只会越来越多，所以不用去左半部分搜索，从而缩小搜索范围，降低时间复杂度。
• 反之说明 $mid$ 的高度太高无法切够木材，$mid$ 都高了大于 $mid$ 的高度必然也都无法得到足够的木材。

二分答案的模板

确立二分的内容

这部分简单的题目通常是求什么就二分什么，当然需要我们自己分析一下二分的内容是否满足单调性，例如本题的锯片高度即满足。

确定二分的范围

即设置 $l,r$ 的大小。这部分不在像数组一样不是直接设定 $l = 1, r = n$。回到本题，我们需要思考的是锯片高度最小可能是多少，最大又可能是多少，这两个值将作为我们的边界赋值给 $l,r$。

根据数据范围，锯片高度最小可以设定为 $1$，最大应该是 $10^9$（实际到不了 $10^9$ 因为所有树的高度取不到 $10^9$）。

编写检查函数和边界的缩小

在本题中，我们二分的值得含义是锯片的高度，我们需要 验证，验证在锯片高度为 $mid$ 的时候，是否可以得到至少 $m$ 米的木材，这部分通常使用一个函数来实现。

若满足条件，则我们需要继续缩短二分的范围，由于本题我们需要求解的锯片高度 尽可能的大，所以若 $mid$ 作为高度可以实现要求，我们应当 $l = mid + 1$ 以此来让后续验证更高的锯片高度。同时满足条件的时候记录答案即可。

最后可能得到的木材数量会爆 int 注意 long long。

总结

• 二分答案更多的是一类题型，可以看出是针对暴力枚举的一种优化。
• 解题的关键往往在于思考暴力如何实现，同时思考能否通过二分加速枚举的过程。
• 需要记住一些关键字眼有助于解题：最短的最大，最小的最大，最大的最小等。

模板代码

#include<bits/stdc++.h>
using namespace std;
bool check(int h) // 检查锯片高度是 h 的时候能否切够至少 M 米 木材 
{
	// 检查函数复杂度：O(n) 
	long long sum = 0;
	for (int i = 1; i <= n; i++) 
	{
		if (a[i] > h) sum += a[i] - h;
	}
	if (sum >= m) return 1; // 木材总和大于等于 m 说明 h 符合要求返回 true 
	return 0;
} 
int main()
{
	int l = 0, r = 1e9, ans = 0; // 一：设定二分范围，根据二分的内容的范围写 
	while (l <= r)
	{
		int mid = (l + r) / 2;
		if (check(mid)) // mid 作为锯片高度可以得到 m 米木材  
		{
			ans = mid; // 记录答案
			l = mid + 1; // 左边更小的锯片高度就不验证了  
		}
		else // 得不到 m 木材 
			r = mid - 1; // 右边更大的高度不验证了 
	} 
	cout << ans;
	return 0;
}

数列分段 Ⅰ

这是一个贪心的问题。由于题目规定数字必须连续分成若干段，那么在每一段的和不超过 $m$ 的情况下，我们应当是能分到一组就尽量都分到一组，如果加入某一个数字 $a_i$ 会超过 $m$，则重新设置一组出来，方便后续的数字分组。

因此具体实现为：

• 维护一个 $sum$ 代表上一组数字的和，同时初始化 $ans=1$ 记录目前所分的组数。
• 接下来对于每一个数字 $a_i$，若 $a_i+sum\leq m$，那么就将 $a_i$ 分到上一组，执行 sum += a[i] 更新上一组的和。
• 否则，新开一组，执行 ans++，同时设定 $sum=a_i$，意思是将 $a_i$ 分到新一组去。

数列分段 Ⅱ

这是一个经典的二分答案将不确定性问题转为判定性问题。

考虑二分答案，即二分每段的和的最大值 $x$，那么这个问题可以转变为：

给你一个 $x$，你需要求出在每段和都不超过 $x$ 的情况下，所分的组数是多少？假如所分的组数不超过题目的限制 $m$，那么说明这个$x$ 合法。

同时 $x$ 也满足单调性可以二分，随着 $x$ 的增大，所分的组数必然是一直减小的。

细节

根据题目数据范围，设定左右端点

int l = 0, r = 1e9 这样是错的。

例如若 $a_i=5$，而 $x=3$，这是不现实的，这样会造成 $a_i$ 没有组可分，请时刻记得 $x$ 的含义是每一组的总和不超过 $x$。

因此左端点的值应当设为 $\max(a_1,a_2,\cdots,a_n)$

或者在 check 函数中做一些限制即可。

在检查函数中，还是做以下情况。

首先初始化 $sum=0$ 维护上一组的和，设定 $ans=1$ 记录所分的组数。初始就有一组故而为 $1$。

接下来啊对于每个数字 $a_i$，分情况处理。

• 若 $a_i>x$，说明这个分组不合理，直接 return 0，请时刻记得 $x$ 的含义是每一组的总和不超过 $x$。
• 若 $a_i+sum\leq x$，说明 $a_i$ 可以分到上一组，执行 sum += a[i]，更新上一组的和。
• 否则执行 ans++，说明新开了一组，同时设定 $sum=a_i$，新开的一组把 $a_i$ 分过去。

循环结束后，根据 $ans$ 和题目给定的 $m$ 的大小关系，来判定 $x$ 是否合法。