跳到主要内容

2023/02/二分答案

· 阅读需 22 分钟
小鱼干
小鱼干
干饭人

目标​

学会二分答案的基本模板，并能进行简单应用。

重点​

二分答案模板的熟悉及对最优性问题转可行性问题的处理。

导图大纲​

回顾​

复习二分查找。

回顾下二分查找的思想，若序列呈升序，我们求出中间值mid，并判断是否满足条件。满足条件输出答案，若不满足将正确答案与mid进行大小的判断，如果比mid大，说明答案在右侧，更新查找区间的最小范围；如果比mid小，说明答案在左侧，更新查找区间的最大范围。

二分查找模板：

int binarySearch(int key,int a[]){
  	int l=MIN,r=MAX;//查找的范围为l~r
    int mid;//存储中间值
    while(l<=r){
        mid=(l+r)/2;//求出中间值
        if(key==a[mid]){//中间值等于要找的
            return mid;//返回key在数组中的位置
        }else if(a[mid]<key){//key比a[mid]大
            //缩小查找范围为右侧
            l=mid+1;//更新最小范围
        }else{//key比a[mid]小
            //缩小范围为左侧
            r=mid-1;//更新最大范围
        }
    }
    return -1;//值不存在
}

引入​

在进行查找的时候，若我们在有序的数列中查找某个符合条件的值，可以采用二叉查找的方式快速的求解内容。二分查找的时间复杂度为

O(logn)O(logn)。而对题目做修改，修改成，查找某个符合某个条件的值的最大或最小的值。此时，套用之前的二分查找的模板就不能够方便地去查找它的位置了。

用之前的模板去进行查找，只能找到某个满足条件的值，而在此基础上的找满足条件的最优值的处理，该算法模板便无能为力了。

此时，我们引入二分答案，来解决此类问题。

二分答案类问题抽象​

形如这样的问题“求在有序的对象中，满足某个条件C(x)的最小的x”。

有序性的广义化​

能用二分答案的问题需要有序，这儿的有序不是传统意义上的值从小到大或者是值从大到小的排列。从数学的角度去理解“有序”，可以理解为：若是升序，那么对任意满足C(x)的x，如果所有的

x′≥xx'\geq x也满足C(x')。说是降序，那么对任意满足C(x)的x，如果所有的x′≤xx'\leq x也满足C(x')。

所有满足以上条件的数列对象，可以称之为有序的。

二分答案的模板​

  • 最小化问题
  • 最大化问题

若我们要求“在有序对象中，满足某个条件C(x)的最小的x”。首先，我们将区间的左端点初始化为不满足C(x)的话，右端点初始化为满足C(x)的值（升序）。然后每次取中点

mid=(lb+rb)/2mid=(lb+rb)/2，判断C(mid)是否满足条件，若满足条件，那么更大的值就不用去找，因为它们都满足条件C(x)，缩小范围，在更小的值中寻找是否有更小的满足条件的值；

如果不满足条件，则更小的值就不用找,因为它们都不满足条件C(x)，缩小范围，在更大的值中寻找是否有满足条件的值。

最小化模板代码

int lb=MIN,rb=MAX;//确定答案的最小、最大范围。
int ans=-1;//最优值位置
while(lb<=rb){//在范围内进行寻找
    int mid=(lb+rb)/2;//求中间值
    if(check(mid)){//判断是mid是否满足条件C
        ans=mid;//满足条件，则更新结果
        rb=mid-1;//寻找满足条件的最小值，故在更小的范围内继续寻找
        //缩小寻找范围： lb ~ mid-1
    }else{//不满足条件，则在更大的范围内寻找能满足条件的值
        lb=mid+1;//缩小寻找范围: mid+1 ~ rb
    }
    cout<<ans;//输出满足条件的最小的值
}

若我们要求“在有序对象中，满足某个条件C(x)的最大的x”。首先，我们将区间的左端点初始化为满足C(x)的话，右端点初始化为不满足C(x)的值。然后每次取中点mid=(lb+rb)/2mid=(lb+rb)/2，判断C(mid)是否满足条件，若满足条件，那么更小的值就不用去找，因为x比它们都大，我们要缩小范围，在更大的值中去寻找满足条件的值。

若不满足条件，那么右侧更大的值就不用去找，因为都不满足，我们缩小范围，在左侧更小的之中寻找满足条件的值。

最大化模板代码

int lb=MIN,rb=MAX;//确定答案的最小、最大范围。
int ans=-1;//最优值位置
while(lb<=rb){//在范围内进行寻找
    int mid=(lb+rb)/2;//求中间值
    if(check(mid)){//判断是mid是否满足条件C
        ans=mid;//满足条件，则更新结果
        lb=mid+1;//寻找满足条件的最大值，故在更大值的范围内继续寻找
        //缩小寻找范围： mid+1 ~ rb
    }else{//不满足条件，则在更小值的范围内寻找能满足条件的值
        rb=mid-1;//缩小寻找范围: l ~ mid-1
    }
    cout<<ans;//输出满足条件的最大的值
}

通过具体题目进行模板的理解​

  • 木材加工

查看例题 木材加工

思考

  1. 题目的最终要求是什么？
  2. 属于二分答案问题吗？由哪些信息得到？
  3. 解题思路是什么？

分析：

本题需要去寻找能够切割得到的小段的最大长度。小段长度，最短可以是1cm，最长可以是最长的一根的长度。对于长度，越短，能获得的小段数量越多；越长，能获得的小段数量越少，此时有序。故，是一个最大化问题。可以采用二分答案的模板。

再思考，二分答案问题中的重点，需要满足的条件是什么？本道题是能够得到k段木头。所以我们要做的就是满段以某个长度切割，能否得到k段木头。

累加每根木头能够切割得到的小段数量。将总数与k进行比较，大于等于k即说明能够获得k段木头。

满足条件，值越大越好，所以缩小范围到

mid+1 ~ rb，否则，缩小范围至 lb ~ mid-1。

#include<iostream>
#include<algorithm>
using namespace std;
int n, k;
int a[100005];
bool check(int m){
	int cnt = 0;
	for (int i = 1; i <= n; i++)
		cnt += a[i] / m;
	return cnt>=k;
}
int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int lb = 1, rb = 100000000, mid, ans = 0;
    while (lb <= rb) { //模板
        mid = (lb + rb) / 2;
        if (check(mid)) {
            ans = mid;
            lb = mid + 1;
        } else{
			rb = mid - 1;
		}
    }
    cout << ans;
    return 0;
}

小结

稍微回顾下本小结的内容，复习了二分查找，学习了基础的二分答案的模板，可用于处理最大化问题和最小化问题，并练习木材加工，这道题，注意对模板的使用。

最优性问题到可行性问题，check()函数的实现思考​

在二分答案类型的题目中，对于check(x)函数的思考和处理是最关键的。不同的题目整体框架相似，但是check(x)函数是不一样的。

check()函数代表的是判断是否满足条件。问题无论是最大化问题还是最小化问题，我们要做的就是将最优化问题，转换成可行性问题。

例如，将求能够切割得到的最长的小段的长度转成能否切割得到k段木头。一般对于可行性问题的转换，我们通常是去思考，题目要我们达成的最基础的条件是什么？题目是满足某个条件的基础上，再进行更优的选择。这一步需要对题目仔细的阅读。找到可行性问题之后，用check(x)去判断是否满足即可。

满足条件时，对缩小范围的处理。​

对于最大化问题与最小化问题，我们结合可行性问题的判断，再来思考下范围的缩小过程。

若是最大化问题，则是满足基础条件的情况下，值越大越好，故每次判断成功，都是缩小范围至右侧值更大的区域内。

若是最小化问题，则是满足基础条件的情况下，值越小越好，故每次判断成功，都是缩小范围至左侧值更小的区域内。

*另一种二分模板​

在前面的模板中，我们使用额外的变量ans来存储最优值，实际上也可以不使用额外的变量，可以使用区域边界来存放最优值。

最小化问题模板

int lb=MIN,rb=MAX;//初始化查找的范围
	int mid;//不需要额外的ans记录答案，使用端点记录最小值
	while(l<r){//不需要等于
		mid=(lb+rb)/2;//求中间值
		if(check(mid)){//判断是否满足条件 C(x)
			rb=mid;//因为要求满足条件的最小值，故缩小范围至更小的部分。使用右端点记录答案，故不需要赋值为mid-1
		}else{
			lb=mid+1;//否则，缩小范围至更大的部分
		}
	}
	return rb;//最小值答案存储在rb中，故返回答案。

最小化问题中，若mid满足条件，此时值要越小越好，故范围缩小至左侧值更小的部分，

rb=某个值，此时使用端点存储答案，所以将mid也包含进去。即 r=mid。循环结束时，最优值存放在端点r中。

最大化问题模板

int lb=MIN,rb=MAX;//初始化查找的范围
	int mid;//不需要额外的ans记录答案，使用端点记录最小值
	while(l<r){//不需要等于
		mid=(lb+rb+1)/2;//求中间值 注意要+1, 考虑 类似这样的情况 lb=1,rb=2,且满足条件
		if(check(mid)){//判断是否满足条件 C(x)
			lb=mid;//因为要求满足条件的最大值，故缩小范围至更大的部分。使用左端点记录答案，故不需要赋值为mid+1
		}else{
			rb=mid-1;//否则，缩小范围至更大的部分
		}
	}
	return lb;//最小值答案存储在lb中，故返回答案。

在最大化问题中，若mid满足条件，此时值要越大越好，故范围缩小至右侧值更大的部分，

lb=某个值，此时使用端点存储答案，所以将mid也包括进去。即 l=mid。循环结束时，最优值存放在端点l中。

两种模板都可行，且时间复杂度都为

O(logn)O(logn)。故，根据习惯选取一种即可。在初赛中两种模板都曾考过，所以要能区分。

思考区别

区别在于三处：

  1. while循环条件一种需要等于；一种不需要等于
  2. 当满足条件时，一种存储至ans中，且区间端点更新为mid±1mid\pm 1;一种区间端点更新为midmid
  3. 循环结束时，一种最优值存储在ans中；一种最优值存储在第二处更新的端点中

题目练习​

思考

  1. 题目的最终要求是什么？
  2. 属于二分答案问题吗？由哪些信息得到？
  3. 解题思路是什么？

分析：

本题需要求砍树的最高高度。高度最低为0，最高为最高的一棵树的高度。高度越高得到的木材越少，高度越低，得到的木材越多。所以高度是有序的。即在有序对象上求的最优值。故可以采用二分答案的最大化问题算法处理。

此时，再思考可行性问题是什么？本题需要满足的基础条件是，砍伐获得m米的木材，故以某高度砍伐能否获得m米的木材即可行性问题。

累加每段数目能获得的木材长度，将总长度与m进行比较，大于等于m则满足条件。

此时满足条件的基础上，值越大越好，故范围缩小至右侧值更大的区域内，否则，范围缩小至左侧值更小的区域内。

#include <iostream>
#include <cstdio>
using namespace std;
int n,m;
int tree[1000005];

bool check(int h){
	//判断以h高度砍树，能否获得m米的木材
	/*
	思路：一棵树一棵树砍伐，累加获得的木材，根据最后的总量
	判断
	*/
	long long sum=0;
	for(int i=1;i<=n;i++){
		if(tree[i]>h){
			sum+=(tree[i]-h);
		}
	}
	if(sum>=m){//能够获得m米的木材
		return true;
	}else{
		return false;
	}
}

int main(){
	cin>>n>>m;//树木的数量 木材总长度
	for(int i=1;i<=n;i++){//输入每棵树的高度
		cin>>tree[i];
	}
	int l=0,r=1e9;//设定最大，最小范围
	int mid,ans=0;
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid)){//判断是否能够获得m米的木材
			ans=mid;//记录答案
			l=mid+1;//高度越高越好
		}else{
			r=mid-1;
		}
	}
	cout<<ans;
	return 0;
}

需要注意总和的范围，可能会超过int故采用long long 进行存储。

小结

稍微回顾下本小结的内容，讲解了二分答案中对于最优性问题转换成可行性问题的处理，以及介绍了另一种二分答案模板，注意两种模板的区别，不要用混。练习了砍树问题，注意数据范围的问题。

有些题目的可行性问题不是很明显，需要我们仔细阅读题目并进行分析。

进击的奶牛​

思考

  1. 题目的最终要求是什么？
  2. 属于二分答案问题吗？由哪些信息得到？
  3. 解题思路是什么？

分析：

本题要求的是最大的最近距离。最小的距离就是两个紧挨着的牛棚的距离也就是1，最大的距离就是最远的两个牛棚间的距离。思考这个距离对题目产生的影响，距离越近，能安排的牛的数量就越多，距离越远，能安排的牛的数量就越少。从影响到的牛的数量去思考可行性问题，结合题目，可发现共有C头牛。故，check(x)可行性问题是能否安排的下C头牛。

第一个牛棚一定可以安排一头牛，依次遍历牛棚，比较每个牛棚与前一个安排了牛的牛棚的距离,如果距离小于x,则该牛棚无法安排牛，跳过继续下一个。统计最多能安排的牛的总数，将它与C进行比较，能大于等于C则说明可以安排下C头牛。

此时，满足条件的基础上，值越大越好，故范围缩小至右侧值更大的区域，

l=mid+1。否则范围缩小至左侧值更小的区域，r=mid-1。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,c;//隔间的数量 牛的数量
int x[100005];//隔间的位置

bool check(int m){
	//是否能够安排得下c头牛
	/*
	以间隔距离m进行安排，看能安排的牛的总数。
	将总数与c进行比较
	*/
	long long sum=1;
	int last=1;
	for(int i=2;i<=n;i++){
		//i号牛棚能安排下一头牛
		if(x[i]-x[last]>=m){
			sum++;
			last=i;
		}
	}

	if(sum>=c){
		return true;
	}else{
		return false;
	}
}

int main(){
	cin>>n>>c;
	for(int i=1;i<=n;i++){
		cin>>x[i];
	}
	sort(x+1,x+1+n);
	int l=1,r=1000000000;
	int mid,ans=0;
	while(l<=r){
		mid=(l+r)/2;//求平均数
		if(check(mid)){//判断是否满足基础要求
			ans=mid;
			l=mid+1;
		}else{
			r=mid-1;
		}
	}
	cout<<ans;
	return 0;
}
奶牛晒衣服​

思考

  1. 题目的最终要求是什么？
  2. 属于二分答案问题吗？由哪些信息得到？
  3. 解题思路是什么？

分析：

本题要求的是弄干所有衣服的最少时间。最少时间1秒，最多时间即每件衣服自然烘干的总时间。思考时间对题目产生的影响，时间越少，湿度去的越少，能晾干的衣服越少;时间越多，湿度去的越多，能晾干的衣服越多。从晾干的衣服的件数去思考可行性问题，结合题目，可发现共有n件衣服。故,check(x)可行性问题是能否在时间限制内晾干所有衣服。

先计算该时间限制内自然晾干的湿度，再计算剩下的衣服用烘干机需要的时间。将总时间与限制时间进行比较，若小于等于x则说明能在时间限制内完成晾干所有的衣服。

此时，此时，满足条件的基础上，值越小越好，故范围缩小至左侧值更小的区域，

=mid-1。否则范围缩小至右侧值更大的区域，l=mid+1。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
long long n,a,b;//a-自然晾干 b-烘衣机
long long w[500005];
bool check(int m){
	//在m时间限制内，是否能晾干所有的衣服
	long long sum=0;//使用烘衣机的时间
	for(int i=1;i<=n;i++){
		if(m*a>=w[i]){//能够自然晾干
			continue;
		}else{
			sum+=ceil(1.0*(w[i]-a*m)/b);//额外的用烘干机晾干
		}
	}
	if(sum<=m){
		return true;
	}else{
		return false;
	}
}
int main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}

	int l=1,r=500000;
	int ans=0,mid;
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	cout<<ans;
	return 0;
}

小结​

二分答案用于求在有序数列上的最优值问题。问题关键是将最优化问题转成可行性问题。给出了两种算法模板，需要熟记下来，并能够熟练地进行应用。多去思考题目最终要去求什么以及需要达成的基础条件是什么。