C++（二分答案）

分享内容

1. 二分答案的原理
2. 二分答案的应用场景
3. 二分答案实例

常用操作系统简介(三)

Android:一种基于Linux内核的自由及开放源代码的移动操作系统。主要用于智能手机和平板
电脑等移动设备。
ios:由苹果公司开发的操作系统,用于iPhone和iPad等设备,具有流畅的用户体验和丰富的应用生态。
这些操作系统在功能上各有特色,Windows和Mac OS提供了丰富的用户界面和广泛的 应用支持,UNIX、Linux以其强大的系统管理和可移植性著称,而Android和iOS则在移动设备市场中占据主导地位。

二分答案的概念

● 二分答案也是二分法的一种应用
● 二分答案的思路不是直接得到答案,而是反复的验证某个答案是
否符合要求,从而不断缩小答案可能的范围,直到把这个范围缩
小到1,即可得到答案
● 大多数情况下用于求解满足某种条件的最大(小)值
二分答案的应用场景

二分答案法适合解决满足以下特点的问题

1. 问题的目标是:给定条件c(x),求满足条件c(x)的x的最小值(或最大值)
2. 比较容易确定x的粗略的取值范围
3. 在这个范围内存在一个临界点x=ans,把区域分成满足条件和不满足条件两个区间。

①<ans的x值都不满足条件c(x),>=ans的x值都满足条件
不满足条件 —ans—满足条件----------->ans是“大值中的最小值”

② <= ans的x值都满足条件C(x),>ans的x值都不满足条件C(x)、
满足条件—ans—不满足条件-------->ans是“小值中的最大值”

ans 就是要找的答案!

二分答案的优势

● 如果一个问题有上面的特点,就适合用二分答案法
● 二分答案法因为其二分特性,比顺序查找(暴力枚举)法更高效
● 二分答案法更适合查找范围比较大,并且对运行时间有要求的竞赛题
● 如果只求正确性,不要求效率,同类问题一般也可以用暴力枚举、模拟法求解

卡车装货

现在有n组货物需要通过卡车运送,每组货物的量可以用一个整数ai表示。我们用数组a=[a1,a2,…,an]表示n组货物的量。每辆卡车的运载量为一个固定的整数k。运送货物时,一组货可以被分到多量卡车上进行运送,但是,不同组的货不能混装到同一辆卡车上。问题为:如果想要同时运送所有的n组货物,至少需要多少辆卡车?

有两组货物,货物量为7和5。卡车的运送量k为3。
用一段黑色线段表示一辆卡车。
那么,两组货物一共需要3+2=5辆卡车。

· 货物量为ai的组至少需要ceil(ai/k)辆卡车来运输
· 所以需要卡车总数是sum(ceil(ai/k))

卡车装货-进阶

现在有n组货物需要通过卡车运送,每组货物的量可以用一个整数ai表示。我们用数组a=[a1,a2,…,an]表示n组货物的量。一组货可以被分到多辆卡车上进行运送,但是,不同组的货不能混装到同一辆卡车上。现在我们希望所有的货物可以用至多m辆卡车来运送。问:当卡车的运载量最少为多少时可以满足这一要求?(输入数据保证问题一定有解)。
专

暴力枚举也可以解这个问题,但是效率不高,优先考虑用二分答案法!
问题从“已知卡车运载量求卡车数量”变为“已知n组货物和卡车数量m,求满足条件的最小的卡车运载量?”

要满足的条件是:m辆卡车能按题目的规则装下指定的n组货物

假设在运载量为ans的时候,刚好用m辆车完成运送,那么

· 当运载量变为更大时,我们依旧可以采用上述方案来运输,相
当于把每辆车多出来的运载量闲置不用。
· 反之运载量变为更小时,一定是不能完成任务的。

条件验证函数c(x)代码示例:卡车载货量x的情况下,m辆卡车如果能装完a[]指定的货,则返回true,否则返回false。

boolC(intx){//假设数组a[]和变量n、m都是全局变量intcnt=0;// 计算装完n组货至少需要多少量卡车for(inti=1;i<=n;i++)cnt+=(a[i]+x-1)/x;//正整数相除的向上取整的技巧if(cnt>m)//需要的卡车数量>m,即m辆车装不下returnfalse;//ceil((a[i]*1.0)/x)或者先转浮点elsereturntrue;}c(x)的时间复杂度为O(n)

二分查找函数的代码示例:在min~max中二分查找使C(x)成立的最小值

intfind(intmin,intmax){intleft=min,right=max;// 初始查找范围intans;while(left<=right){intmid=(left+right)/2;// 中间数的位置if(C(mid)){//条件成立,答案在左半区间right=mid-1;ans=mid;// 记录可能的答案}else// 条件不成立,答案在右边区间left=mid+1;// 最终答案在ans中----找到的是满足条件的最小值returnans;find函数的时间复杂度为O(nlogM)M是初始范围[min,max]的大小

用暴力枚举法也可以求出这个最小值但是时间复杂度是O(nM)

二分答案的解题步骤(求最小值)

使用二分答案法来求解最小值的具体过程为:

1. 定义条件验证函数c(x)
2. 粗略的确定x的取值范围,保证答案一定落在这个范围内。
3. 进行二分查找:假设范围[L,R]的中间值是mid
   ①我们验证mid是否满足条件,即c(mid)的真假,更新答案和边界:
   如果c(mid)=true,说明mid>=答案,这种情况先记录mid作为备选答案ans,同时更新边界:R=mid-1。
   如果c(mid)=false,说明m<答案,这种情况只要更新边界:L=mid+1。
   ② 不断重复第1步来缩小范围,直到L>R。
4. 此时,ans就是我们需要寻找的最小值。

如果用二分答案法求最大值,要以相反的方式更新边界

二分答案模版代码

● 我们经常判断不好边界条件,导致实现二分算法耗时太长

● 分情况来模板化代码,有利于我们长期记忆和加深理解

● 记住模板、熟练套用模块后,find()函数背模板代码就可以,只需要写出正确

的Check函数

◆二分查找函数的模板代码有多种正确的写法,本课程提供的是其中之一

◆ Check函数则需要根据题目的描述具体实现,基本没有模式可循

二分查拌 v5 二分答案

二分查找和二分答案都利用了二分的思想,但它们在应用场景和实现方式上有所不同
● 应用范围:
二分查找:主要用于在有序数组中查找目标值。
二分答案:用于找到一个满足特定条件的最优值,如“最小的最大值”或“最大的最小值”问题。
实现细节:
二分查找:通过比较数组中的中间元素和目标值来确定搜索范围的缩小方向。
二分答案:通过设计一个验证函数,来检查当前的中点值是否满足问题的条件,然后根据验证结果来调整搜索范围。

伐木问题

n棵树(n≤10^{6)高度分别为a1…an(树高不超过10}9),对于一个砍树高度h,可以锯下并收集到每棵树上比h高的部分的木材。求最大的整数砍树高度h,使得能够收集到木材总长度至少为m米。所有木材长度之和大于m,因此必有解。
【输入】
第1行:2个整数n和m,n表示树木的数量,m表示需要的木材总长度。
第2行:n个整数表示每棵树的高度。
【输出】1个整数,表示砍树的最高高度。
【输入样例】

5 20

4 42 40 26 46

【输出样例】

36

理解

题目中的条件:“最大的整数砍树高度h,使得能够收集到木材总长度至少为m米”可定义c(h):砍树高度为h时,从n棵数砍下的总木材长度=sum(ai-h),如果>=m,返回true,否则false。

· 最小的高度--------h=0------------sum(ai)-----------所有木材长度之和大于m(满足条件)
·最大的高度--------h=max(ai)------------0-----------一定不满足条件

可见,h越小越容易满足总木材长度>=m。且存在某一个临界点ans,把区间二分成满足和不满足左右两部分。

这是一个“求小值中的最大值”的问题

使得C(h)=True的最大值就是答案,适合用二分答案法解题!

使用二分答案法来求解最大值的具体过程为:

1. 定义条件验证函数c(x)
2. 粗略的确定x的取值范围,保证答案ans一定落在这个范围内。
3. 进行二分查找:假设范围[L,R]的中间值是mid
   ①我们验证mid是否满足条件,即c(mid)的真假,更新答案和边界:
   如果C(mid)=true,说明mid>=答案,这种情况先记录mid作为备选答案ans,同时更
   新边界:L=mid+1。
   如果c(mid)=false,说明m<答案,这种情况只要更新边界:R=mid-1。
   ② 不断重复第1步来缩小范围,直到L>R。
4. 此时,ans就是我们需要寻找的最大值。

条件函数Check(h)代码示例:

· 树的高度在数组a[]中,且a[]和变量n、m都是全局变量

boolCheck(inth){longlongtot=0;for(inti=1;i<=n;i++)if(a[i]>h)tot+=a[i]-h;//按照题意模拟。returntot>=m;}

Check(h)的时间复杂度为O(n)

二分查找函数代码示例:在[min,max]间二分查找使Check(h)成立的最大值

intfind(intmin,intmax){intleft=min,right=max;// 初始查找范围intans;while(left<=right){intmid=(left+right)/2;if(Check(mid)){// 条件成立,答案在右半区间left=mid+1;ans=mid;// 记录可能的答案}else// 条件不成立,答案在左半区间right=mid-1;}// 最终答案在ans中returnans;}find函数的时间复杂度为O(nlogM)M是初始范围[min,max]的大小

完整代码

#include<iostream>usingnamespacestd;inta[100010];//树的高度数组intn,m;// 条件函数Check(h)当砍树高度为h时能否得到大于m的木材boolCheck(inth){longlongtot=0;for(inti=1;i<=n;i++)if(a[i]>h)tot+=a[i]-h;//按照题意模拟。returntot>=m;}//在[min,max]之间二分查找使 Check()成立的答案(最大值)intfind(intmin,intmax){intleft=min,right=max;// MATt1U21intans;while(left<=right){intmid=(left+right)/2;if(Check(mid)){//条件成立,答案在右半区间left=mid+1;ans=mid;//记录可能的答案}else{// 条件不成立,答案在左半区间right=mid-1;}}// 最终答案在ans中returnans;}intmain(){intmax=0;cin>>n>>m;for(inti=1;i<=n;i++){cin>>a[i];if(a[i]>max)max=a[i];//找到最高的树的高度}cout<<find(0,max);return0;}

愤怒的奶牛

Farmer John建造了一个有N(2 <= N <= 100,000)个隔间的牛棚,这些隔间分布在一条直
线上,坐标是x1,…,xN(0 <= xi <= 1,000,000,000)。
他的C(2 <= C <= N)头牛不满于隔间的位置分布,它们为牛棚里其他的牛的存在而愤怒。
为了防止牛之间的互相打斗,Farmer John想把这些牛安置在指定的隔间,所有牛中相
邻两头的最近距离越大越好。那么,这个最大的最近距离是多少呢?
【输入】第1行:两个用空格隔开的数字N和C。
第2行:N个整数,表示每个隔间的坐标。
【输出】输出只有一行,即相邻两头牛最大的最近距离。
【输入样例】
5 3

1 2 8 4 9

【输出样例】3

二分查找函数代码示例:在[min,max]间二分查找使Check(x)成立的最大值intfind(intmin,intmax){intleft=min,right=max;// 初始查找范围intans;while(left<=right){intmid=(left+right)/2;//中间数的位置if(Check(mid)){// 条件成立,答案在右半区间left=mid+1;ans=mid;// 记录可能的答案}else// 条件不成立,答案在左半区间right=mid-1;}//最终答案在ans中returnans;}find函数的时间复杂度为O(nlogM)M是初始范围[min,max]的大小

条件是:“把c头牛全部安置进N个隔间,而且相邻两头牛距离>=x”
如何定义和实现条件判断函数Check()?

可以大致感受到一种贪心算法:从最左端开始遍历所有安置点,能安置就安置。
容易证明,在本题中,安置一定比不安置更优,贪心正确。
定义Check(x):
如果能在n个隔间放下c头牛,并且相邻牛的距离总是>=x,则返回true,否则返回false。
具体实现步骤:

1. 遍历所有隔间:如果当前隔间与上一头牛所在隔间距离>=x,则安置一头牛,已安置计数+1。
2. 判断已安置计数>=C,返回true,否则返回false。

【注意】这个算法的前提是所有隔间已经按位置排序

条件函数Check(x)代码示例:· 假设a[]和变量n、c都是全局变量,且a[]数组数据已经按升序排序boolCheck(intx){// k:已安置数量;last:记录上一头牛的安置坐标intk=1,last=a[1];//第1头牛总是可以安置的for(inti=2;i<=n;i++)if(a[i]-last>=x){// 与上一头牛间隔>=x,能安置last=a[i];//安置一头,更新lastk++;// 安置数量+1}returnk>=c;}时间复杂度O(n)

#include<iostream>#include<algorithm>usingnamespacestd;inta[100010];// 隔间坐标数组intn,c;// 条件函数Check(x)最近距离是x时能否在n个隔间放下c头牛boolCheck(intx){//k:已安置数量;last:记录上一头牛的安置坐标intk=1,last=a[1];//第1头牛总是可以安置的for(inti=2;i<=n;i++)if(a[i]-last>=x){//与上一头牛间隔>=x,能安置last=a[i];//安置一头,更新lastk++:// 安置数量+1}returnk>=c;}//在[min,max]之间二分查找使Check()成立的最大值intfind(intmin,intmax){intleft=min,right=max;// 初始查找范围intans;while(left<=right){intmid=(left+right)/2;if(Check(mid)){//条件成立,答案在右半区间left=mid+1;ans=mid;// 记录可能的答案}else{// 条件不成立,答案在左半区问right=mid-1;}}// 最终答案在ans中returnans;}intmain(){cin>>n>>c;for(inti=1;i<=n;i++){cin>>a[i];}// 先排序(升序)sort(a+1,a+n+1);cout<<find(0,a[n]);return0;}

【注意】
· 由于输入的隔间位置不保证有序,所有在进行二分查找前需要先对数组进行排序
· 使用sort函数需要包含头文件
· 排序后最大的a元素排最后,可以作为查找的右边界

本次课程的知识点

1. 二分答案的原理、应用场景

2. 卡车装货演示如何用二分答案求解最小值

3. 二分答案的两种场景的模板:找最小值、最大值

4. 二分答案编程练习:伐木问题(找最大值)、愤怒的奶牛

1、下列软件中是操作系统的是(c )?

A、高德地图

B、腾讯会议

C、纯血鸿蒙

D、金山永中
2、下面C++代码执行后输出是()?

intN=0,i;for(i=1;i<10;i++)N+=1;cout<<(N+i);

A, 54

B. 20

C.19

D. 18

礼盒的最大甜蜜度

商店有n种糖果,每种糖果的价格分别为ai(其中i=1,2,…,n),(2 <= n <= 100,000)。
商店需要组合k类不同糖果打包成礼盒出售。礼盒的甜蜜度是礼盒中任意两种糖果价格绝
对差的最小值。问题:求满足打包要求的礼盒的最大甜蜜度。
【输入】第1行:两个用空格隔开的数字n和k。
第2行:n个整数,表示每种糖果的价格。
【输出】输出只有一行,即满足打包要求的礼盒的最大甜蜜度。
【输入样例】

6 3

13 5 1 8 21 2

【输出样例】
8

思路:这是二分答案找最大值的问题!

· 定义check()函数检查在最大甜蜜度为x的情况下,是否可以找到k类不同糖果,使得两两价格绝对差的最小值大于等于x;
· 为了方便计算价格差,需要先对糖果按价格排序;
· 最大甜蜜度x的范围:最小0,最大可以取最贵的糖果的价格。

#include<iostream>finclude<algorithm>usingnamespacestd;inta[100010];intn,k;// check()函数检查在最大甜宝度为x的情况下,是否可以找到k类不同糖果,// 使得两两价格绝对差最小值大于等于x// 需要先对价格排序boolCheck(intx){intfirst=a[1];//4)-FPRFintcnt=1;for(inti=2;i<=n;i++)//价格差满足>=x,可以作为第二种糖打包if(a[i]>=first+x){cnt+=1;first=a[i];}returncnt>k;}//在[min,max]之间二分查找使 Check()成立的答案(最大值)intfind(intmin,intmax){intleft=min,right=max;// MATintans;while(left<=right){intmid=(left+right)/2;if(Check(mid)){//条件成立,答案在右半区问left=mid+1;ans=mid;//记录可能的答案}else{// 条件不成立,答案在左半区问right=mid-1;}}// 最终答案在ans中returnans;}intmain(){cin>>n>>k;for(inti=l;i<=n;i++){cin>>a[i];}// 先排序(升序)sort(a+1,a+n+1);// 二分查找 0~max(a)cout<<find(0,a[n]);return0;}

【注意】二分查找前需要先对价格排序