目标

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

重点

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

导图大纲

回顾

复习二分查找。

回顾下二分查找的思想,若序列呈升序,我们求出中间值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,如果所有的

xxx'\geq x也满足C(x’)。说是降序,那么对任意满足C(x)的x,如果所有的xxx'\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;
}

小结

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

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)