分享内容二分答案的原理二分答案的应用场景二分答案实例常用操作系统简介(三)Android:一种基于Linux内核的自由及开放源代码的移动操作系统。主要用于智能手机和平板电脑等移动设备。ios:由苹果公司开发的操作系统,用于iPhone和iPad等设备,具有流畅的用户体验和丰富的应用生态。这些操作系统在功能上各有特色,Windows和Mac OS提供了丰富的用户界面和广泛的 应用支持,UNIX、Linux以其强大的系统管理和可移植性著称,而Android和iOS则在移动设备市场中占据主导地位。二分答案的概念● 二分答案也是二分法的一种应用● 二分答案的思路不是直接得到答案,而是反复的验证某个答案是否符合要求,从而不断缩小答案可能的范围,直到把这个范围缩小到1,即可得到答案● 大多数情况下用于求解满足某种条件的最大(小)值二分答案的应用场景二分答案法适合解决满足以下特点的问题问题的目标是:给定条件c(x),求满足条件c(x)的x的最小值(或最大值)比较容易确定x的粗略的取值范围在这个范围内存在一个临界点xans,把区域分成满足条件和不满足条件两个区间。①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。用一段黑色线段表示一辆卡车。那么,两组货物一共需要325辆卡车。· 货物量为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都是全局变量intcnt0;// 计算装完n组货至少需要多少量卡车for(inti1;in;i)cnt(a[i]x-1)/x;//正整数相除的向上取整的技巧if(cntm)//需要的卡车数量m,即m辆车装不下returnfalse;//ceil((a[i]*1.0)/x)或者先转浮点elsereturntrue;}c(x)的时间复杂度为O(n)二分查找函数的代码示例:在min~max中二分查找使C(x)成立的最小值intfind(intmin,intmax){intleftmin,rightmax;// 初始查找范围intans;while(leftright){intmid(leftright)/2;// 中间数的位置if(C(mid)){//条件成立,答案在左半区间rightmid-1;ansmid;// 记录可能的答案}else// 条件不成立,答案在右边区间leftmid1;// 最终答案在ans中----找到的是满足条件的最小值returnans;find函数的时间复杂度为O(nlogM)M是初始范围[min,max]的大小用暴力枚举法也可以求出这个最小值但是时间复杂度是O(nM)二分答案的解题步骤(求最小值)使用二分答案法来求解最小值的具体过程为:定义条件验证函数c(x)粗略的确定x的取值范围,保证答案一定落在这个范围内。进行二分查找:假设范围[L,R]的中间值是mid①我们验证mid是否满足条件,即c(mid)的真假,更新答案和边界:如果c(mid)true,说明mid答案,这种情况先记录mid作为备选答案ans,同时更新边界:Rmid-1。如果c(mid)false,说明m答案,这种情况只要更新边界:Lmid1。② 不断重复第1步来缩小范围,直到LR。此时,ans就是我们需要寻找的最小值。如果用二分答案法求最大值,要以相反的方式更新边界二分答案模版代码● 我们经常判断不好边界条件,导致实现二分算法耗时太长● 分情况来模板化代码,有利于我们长期记忆和加深理解● 记住模板、熟练套用模块后,find()函数背模板代码就可以,只需要写出正确的Check函数◆二分查找函数的模板代码有多种正确的写法,本课程提供的是其中之一◆ Check函数则需要根据题目的描述具体实现,基本没有模式可循二分查拌 v5 二分答案二分查找和二分答案都利用了二分的思想,但它们在应用场景和实现方式上有所不同● 应用范围:二分查找:主要用于在有序数组中查找目标值。二分答案:用于找到一个满足特定条件的最优值,如“最小的最大值”或“最大的最小值”问题。实现细节:二分查找:通过比较数组中的中间元素和目标值来确定搜索范围的缩小方向。二分答案:通过设计一个验证函数,来检查当前的中点值是否满足问题的条件,然后根据验证结果来调整搜索范围。伐木问题n棵树(n≤106)高度分别为a1…an(树高不超过109),对于一个砍树高度h,可以锯下并收集到每棵树上比h高的部分的木材。求最大的整数砍树高度h,使得能够收集到木材总长度至少为m米。所有木材长度之和大于m,因此必有解。【输入】第1行:2个整数n和m,n表示树木的数量,m表示需要的木材总长度。第2行:n个整数表示每棵树的高度。【输出】1个整数,表示砍树的最高高度。【输入样例】5 204 42 40 26 46【输出样例】36理解题目中的条件:“最大的整数砍树高度h,使得能够收集到木材总长度至少为m米”可定义c(h):砍树高度为h时,从n棵数砍下的总木材长度sum(ai-h),如果m,返回true,否则false。· 最小的高度--------h0------------sum(ai)-----------所有木材长度之和大于m(满足条件)·最大的高度--------hmax(ai)------------0-----------一定不满足条件可见,h越小越容易满足总木材长度m。且存在某一个临界点ans,把区间二分成满足和不满足左右两部分。这是一个“求小值中的最大值”的问题使得C(h)True的最大值就是答案,适合用二分答案法解题!使用二分答案法来求解最大值的具体过程为:定义条件验证函数c(x)粗略的确定x的取值范围,保证答案ans一定落在这个范围内。进行二分查找:假设范围[L,R]的中间值是mid①我们验证mid是否满足条件,即c(mid)的真假,更新答案和边界:如果C(mid)true,说明mid答案,这种情况先记录mid作为备选答案ans,同时更新边界:Lmid1。如果c(mid)false,说明m答案,这种情况只要更新边界:Rmid-1。② 不断重复第1步来缩小范围,直到LR。此时,ans就是我们需要寻找的最大值。条件函数Check(h)代码示例:· 树的高度在数组a[]中,且a[]和变量n、m都是全局变量boolCheck(inth){longlongtot0;for(inti1;in;i)if(a[i]h)tota[i]-h;//按照题意模拟。returntotm;}Check(h)的时间复杂度为O(n)二分查找函数代码示例:在[min,max]间二分查找使Check(h)成立的最大值intfind(intmin,intmax){intleftmin,rightmax;// 初始查找范围intans;while(leftright){intmid(leftright)/2;if(Check(mid)){// 条件成立,答案在右半区间leftmid1;ansmid;// 记录可能的答案}else// 条件不成立,答案在左半区间rightmid-1;}// 最终答案在ans中returnans;}find函数的时间复杂度为O(nlogM)M是初始范围[min,max]的大小完整代码#includeiostreamusingnamespacestd;inta[100010];//树的高度数组intn,m;// 条件函数Check(h)当砍树高度为h时能否得到大于m的木材boolCheck(inth){longlongtot0;for(inti1;in;i)if(a[i]h)tota[i]-h;//按照题意模拟。returntotm;}//在[min,max]之间二分查找使 Check()成立的答案(最大值)intfind(intmin,intmax){intleftmin,rightmax;// MATt1U21intans;while(leftright){intmid(leftright)/2;if(Check(mid)){//条件成立,答案在右半区间leftmid1;ansmid;//记录可能的答案}else{// 条件不成立,答案在左半区间rightmid-1;}}// 最终答案在ans中returnans;}intmain(){intmax0;cinnm;for(inti1;in;i){cina[i];if(a[i]max)maxa[i];//找到最高的树的高度}coutfind(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 31 2 8 4 9【输出样例】3二分查找函数代码示例:在[min,max]间二分查找使Check(x)成立的最大值intfind(intmin,intmax){intleftmin,rightmax;// 初始查找范围intans;while(leftright){intmid(leftright)/2;//中间数的位置if(Check(mid)){// 条件成立,答案在右半区间leftmid1;ansmid;// 记录可能的答案}else// 条件不成立,答案在左半区间rightmid-1;}//最终答案在ans中returnans;}find函数的时间复杂度为O(nlogM)M是初始范围[min,max]的大小条件是:“把c头牛全部安置进N个隔间,而且相邻两头牛距离x”如何定义和实现条件判断函数Check()?可以大致感受到一种贪心算法:从最左端开始遍历所有安置点,能安置就安置。容易证明,在本题中,安置一定比不安置更优,贪心正确。定义Check(x):如果能在n个隔间放下c头牛,并且相邻牛的距离总是x,则返回true,否则返回false。具体实现步骤:遍历所有隔间:如果当前隔间与上一头牛所在隔间距离x,则安置一头牛,已安置计数1。判断已安置计数C,返回true,否则返回false。【注意】这个算法的前提是所有隔间已经按位置排序条件函数Check(x)代码示例:· 假设a[]和变量n、c都是全局变量,且a[]数组数据已经按升序排序boolCheck(intx){// k:已安置数量;last:记录上一头牛的安置坐标intk1,lasta[1];//第1头牛总是可以安置的for(inti2;in;i)if(a[i]-lastx){// 与上一头牛间隔x,能安置lasta[i];//安置一头,更新lastk;// 安置数量1}returnkc;}时间复杂度O(n)#includeiostream#includealgorithmusingnamespacestd;inta[100010];// 隔间坐标数组intn,c;// 条件函数Check(x)最近距离是x时能否在n个隔间放下c头牛boolCheck(intx){//k:已安置数量;last:记录上一头牛的安置坐标intk1,lasta[1];//第1头牛总是可以安置的for(inti2;in;i)if(a[i]-lastx){//与上一头牛间隔x,能安置lasta[i];//安置一头,更新lastk:// 安置数量1}returnkc;}//在[min,max]之间二分查找使Check()成立的最大值intfind(intmin,intmax){intleftmin,rightmax;// 初始查找范围intans;while(leftright){intmid(leftright)/2;if(Check(mid)){//条件成立,答案在右半区间leftmid1;ansmid;// 记录可能的答案}else{// 条件不成立,答案在左半区问rightmid-1;}}// 最终答案在ans中returnans;}intmain(){cinnc;for(inti1;in;i){cina[i];}// 先排序(升序)sort(a1,an1);coutfind(0,a[n]);return0;}【注意】· 由于输入的隔间位置不保证有序,所有在进行二分查找前需要先对数组进行排序· 使用sort函数需要包含头文件· 排序后最大的a元素排最后,可以作为查找的右边界本次课程的知识点二分答案的原理、应用场景卡车装货演示如何用二分答案求解最小值二分答案的两种场景的模板:找最小值、最大值二分答案编程练习:伐木问题(找最大值)、愤怒的奶牛1、下列软件中是操作系统的是(c )?A、高德地图B、腾讯会议C、纯血鸿蒙D、金山永中2、下面C代码执行后输出是()?intN0,i;for(i1;i10;i)N1;cout(Ni);A, 54B. 20C.19D. 18礼盒的最大甜蜜度商店有n种糖果,每种糖果的价格分别为ai(其中i1,2,…,n),(2 n 100,000)。商店需要组合k类不同糖果打包成礼盒出售。礼盒的甜蜜度是礼盒中任意两种糖果价格绝对差的最小值。问题:求满足打包要求的礼盒的最大甜蜜度。【输入】第1行:两个用空格隔开的数字n和k。第2行:n个整数,表示每种糖果的价格。【输出】输出只有一行,即满足打包要求的礼盒的最大甜蜜度。【输入样例】6 313 5 1 8 21 2【输出样例】8思路:这是二分答案找最大值的问题!· 定义check()函数检查在最大甜蜜度为x的情况下,是否可以找到k类不同糖果,使得两两价格绝对差的最小值大于等于x;· 为了方便计算价格差,需要先对糖果按价格排序;· 最大甜蜜度x的范围:最小0,最大可以取最贵的糖果的价格。#includeiostreamfincludealgorithmusingnamespacestd;inta[100010];intn,k;// check()函数检查在最大甜宝度为x的情况下,是否可以找到k类不同糖果,// 使得两两价格绝对差最小值大于等于x// 需要先对价格排序boolCheck(intx){intfirsta[1];//4)-FPRFintcnt1;for(inti2;in;i)//价格差满足x,可以作为第二种糖打包if(a[i]firstx){cnt1;firsta[i];}returncntk;}//在[min,max]之间二分查找使 Check()成立的答案(最大值)intfind(intmin,intmax){intleftmin,rightmax;// MATintans;while(leftright){intmid(leftright)/2;if(Check(mid)){//条件成立,答案在右半区问leftmid1;ansmid;//记录可能的答案}else{// 条件不成立,答案在左半区问rightmid-1;}}// 最终答案在ans中returnans;}intmain(){cinnk;for(intil;in;i){cina[i];}// 先排序(升序)sort(a1,an1);// 二分查找 0~max(a)coutfind(0,a[n]);return0;}【注意】二分查找前需要先对价格排序
C++（二分答案）
发布时间：2026/6/11 21:40:14
分享内容二分答案的原理二分答案的应用场景二分答案实例常用操作系统简介(三)Android:一种基于Linux内核的自由及开放源代码的移动操作系统。主要用于智能手机和平板电脑等移动设备。ios:由苹果公司开发的操作系统,用于iPhone和iPad等设备,具有流畅的用户体验和丰富的应用生态。这些操作系统在功能上各有特色,Windows和Mac OS提供了丰富的用户界面和广泛的 应用支持,UNIX、Linux以其强大的系统管理和可移植性著称,而Android和iOS则在移动设备市场中占据主导地位。二分答案的概念● 二分答案也是二分法的一种应用● 二分答案的思路不是直接得到答案,而是反复的验证某个答案是否符合要求,从而不断缩小答案可能的范围,直到把这个范围缩小到1,即可得到答案● 大多数情况下用于求解满足某种条件的最大(小)值二分答案的应用场景二分答案法适合解决满足以下特点的问题问题的目标是:给定条件c(x),求满足条件c(x)的x的最小值(或最大值)比较容易确定x的粗略的取值范围在这个范围内存在一个临界点xans,把区域分成满足条件和不满足条件两个区间。①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。用一段黑色线段表示一辆卡车。那么,两组货物一共需要325辆卡车。· 货物量为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都是全局变量intcnt0;// 计算装完n组货至少需要多少量卡车for(inti1;in;i)cnt(a[i]x-1)/x;//正整数相除的向上取整的技巧if(cntm)//需要的卡车数量m,即m辆车装不下returnfalse;//ceil((a[i]*1.0)/x)或者先转浮点elsereturntrue;}c(x)的时间复杂度为O(n)二分查找函数的代码示例:在min~max中二分查找使C(x)成立的最小值intfind(intmin,intmax){intleftmin,rightmax;// 初始查找范围intans;while(leftright){intmid(leftright)/2;// 中间数的位置if(C(mid)){//条件成立,答案在左半区间rightmid-1;ansmid;// 记录可能的答案}else// 条件不成立,答案在右边区间leftmid1;// 最终答案在ans中----找到的是满足条件的最小值returnans;find函数的时间复杂度为O(nlogM)M是初始范围[min,max]的大小用暴力枚举法也可以求出这个最小值但是时间复杂度是O(nM)二分答案的解题步骤(求最小值)使用二分答案法来求解最小值的具体过程为:定义条件验证函数c(x)粗略的确定x的取值范围,保证答案一定落在这个范围内。进行二分查找:假设范围[L,R]的中间值是mid①我们验证mid是否满足条件,即c(mid)的真假,更新答案和边界:如果c(mid)true,说明mid答案,这种情况先记录mid作为备选答案ans,同时更新边界:Rmid-1。如果c(mid)false,说明m答案,这种情况只要更新边界:Lmid1。② 不断重复第1步来缩小范围,直到LR。此时,ans就是我们需要寻找的最小值。如果用二分答案法求最大值,要以相反的方式更新边界二分答案模版代码● 我们经常判断不好边界条件,导致实现二分算法耗时太长● 分情况来模板化代码,有利于我们长期记忆和加深理解● 记住模板、熟练套用模块后,find()函数背模板代码就可以,只需要写出正确的Check函数◆二分查找函数的模板代码有多种正确的写法,本课程提供的是其中之一◆ Check函数则需要根据题目的描述具体实现,基本没有模式可循二分查拌 v5 二分答案二分查找和二分答案都利用了二分的思想,但它们在应用场景和实现方式上有所不同● 应用范围:二分查找:主要用于在有序数组中查找目标值。二分答案:用于找到一个满足特定条件的最优值,如“最小的最大值”或“最大的最小值”问题。实现细节:二分查找:通过比较数组中的中间元素和目标值来确定搜索范围的缩小方向。二分答案:通过设计一个验证函数,来检查当前的中点值是否满足问题的条件,然后根据验证结果来调整搜索范围。伐木问题n棵树(n≤106)高度分别为a1…an(树高不超过109),对于一个砍树高度h,可以锯下并收集到每棵树上比h高的部分的木材。求最大的整数砍树高度h,使得能够收集到木材总长度至少为m米。所有木材长度之和大于m,因此必有解。【输入】第1行:2个整数n和m,n表示树木的数量,m表示需要的木材总长度。第2行:n个整数表示每棵树的高度。【输出】1个整数,表示砍树的最高高度。【输入样例】5 204 42 40 26 46【输出样例】36理解题目中的条件:“最大的整数砍树高度h,使得能够收集到木材总长度至少为m米”可定义c(h):砍树高度为h时,从n棵数砍下的总木材长度sum(ai-h),如果m,返回true,否则false。· 最小的高度--------h0------------sum(ai)-----------所有木材长度之和大于m(满足条件)·最大的高度--------hmax(ai)------------0-----------一定不满足条件可见,h越小越容易满足总木材长度m。且存在某一个临界点ans,把区间二分成满足和不满足左右两部分。这是一个“求小值中的最大值”的问题使得C(h)True的最大值就是答案,适合用二分答案法解题!使用二分答案法来求解最大值的具体过程为:定义条件验证函数c(x)粗略的确定x的取值范围,保证答案ans一定落在这个范围内。进行二分查找:假设范围[L,R]的中间值是mid①我们验证mid是否满足条件,即c(mid)的真假,更新答案和边界:如果C(mid)true,说明mid答案,这种情况先记录mid作为备选答案ans,同时更新边界:Lmid1。如果c(mid)false,说明m答案,这种情况只要更新边界:Rmid-1。② 不断重复第1步来缩小范围,直到LR。此时,ans就是我们需要寻找的最大值。条件函数Check(h)代码示例:· 树的高度在数组a[]中,且a[]和变量n、m都是全局变量boolCheck(inth){longlongtot0;for(inti1;in;i)if(a[i]h)tota[i]-h;//按照题意模拟。returntotm;}Check(h)的时间复杂度为O(n)二分查找函数代码示例:在[min,max]间二分查找使Check(h)成立的最大值intfind(intmin,intmax){intleftmin,rightmax;// 初始查找范围intans;while(leftright){intmid(leftright)/2;if(Check(mid)){// 条件成立,答案在右半区间leftmid1;ansmid;// 记录可能的答案}else// 条件不成立,答案在左半区间rightmid-1;}// 最终答案在ans中returnans;}find函数的时间复杂度为O(nlogM)M是初始范围[min,max]的大小完整代码#includeiostreamusingnamespacestd;inta[100010];//树的高度数组intn,m;// 条件函数Check(h)当砍树高度为h时能否得到大于m的木材boolCheck(inth){longlongtot0;for(inti1;in;i)if(a[i]h)tota[i]-h;//按照题意模拟。returntotm;}//在[min,max]之间二分查找使 Check()成立的答案(最大值)intfind(intmin,intmax){intleftmin,rightmax;// MATt1U21intans;while(leftright){intmid(leftright)/2;if(Check(mid)){//条件成立,答案在右半区间leftmid1;ansmid;//记录可能的答案}else{// 条件不成立,答案在左半区间rightmid-1;}}// 最终答案在ans中returnans;}intmain(){intmax0;cinnm;for(inti1;in;i){cina[i];if(a[i]max)maxa[i];//找到最高的树的高度}coutfind(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 31 2 8 4 9【输出样例】3二分查找函数代码示例:在[min,max]间二分查找使Check(x)成立的最大值intfind(intmin,intmax){intleftmin,rightmax;// 初始查找范围intans;while(leftright){intmid(leftright)/2;//中间数的位置if(Check(mid)){// 条件成立,答案在右半区间leftmid1;ansmid;// 记录可能的答案}else// 条件不成立,答案在左半区间rightmid-1;}//最终答案在ans中returnans;}find函数的时间复杂度为O(nlogM)M是初始范围[min,max]的大小条件是:“把c头牛全部安置进N个隔间,而且相邻两头牛距离x”如何定义和实现条件判断函数Check()?可以大致感受到一种贪心算法:从最左端开始遍历所有安置点,能安置就安置。容易证明,在本题中,安置一定比不安置更优,贪心正确。定义Check(x):如果能在n个隔间放下c头牛,并且相邻牛的距离总是x,则返回true,否则返回false。具体实现步骤:遍历所有隔间:如果当前隔间与上一头牛所在隔间距离x,则安置一头牛,已安置计数1。判断已安置计数C,返回true,否则返回false。【注意】这个算法的前提是所有隔间已经按位置排序条件函数Check(x)代码示例:· 假设a[]和变量n、c都是全局变量,且a[]数组数据已经按升序排序boolCheck(intx){// k:已安置数量;last:记录上一头牛的安置坐标intk1,lasta[1];//第1头牛总是可以安置的for(inti2;in;i)if(a[i]-lastx){// 与上一头牛间隔x,能安置lasta[i];//安置一头,更新lastk;// 安置数量1}returnkc;}时间复杂度O(n)#includeiostream#includealgorithmusingnamespacestd;inta[100010];// 隔间坐标数组intn,c;// 条件函数Check(x)最近距离是x时能否在n个隔间放下c头牛boolCheck(intx){//k:已安置数量;last:记录上一头牛的安置坐标intk1,lasta[1];//第1头牛总是可以安置的for(inti2;in;i)if(a[i]-lastx){//与上一头牛间隔x,能安置lasta[i];//安置一头,更新lastk:// 安置数量1}returnkc;}//在[min,max]之间二分查找使Check()成立的最大值intfind(intmin,intmax){intleftmin,rightmax;// 初始查找范围intans;while(leftright){intmid(leftright)/2;if(Check(mid)){//条件成立,答案在右半区间leftmid1;ansmid;// 记录可能的答案}else{// 条件不成立,答案在左半区问rightmid-1;}}// 最终答案在ans中returnans;}intmain(){cinnc;for(inti1;in;i){cina[i];}// 先排序(升序)sort(a1,an1);coutfind(0,a[n]);return0;}【注意】· 由于输入的隔间位置不保证有序,所有在进行二分查找前需要先对数组进行排序· 使用sort函数需要包含头文件· 排序后最大的a元素排最后,可以作为查找的右边界本次课程的知识点二分答案的原理、应用场景卡车装货演示如何用二分答案求解最小值二分答案的两种场景的模板:找最小值、最大值二分答案编程练习:伐木问题(找最大值)、愤怒的奶牛1、下列软件中是操作系统的是(c )?A、高德地图B、腾讯会议C、纯血鸿蒙D、金山永中2、下面C代码执行后输出是()?intN0,i;for(i1;i10;i)N1;cout(Ni);A, 54B. 20C.19D. 18礼盒的最大甜蜜度商店有n种糖果,每种糖果的价格分别为ai(其中i1,2,…,n),(2 n 100,000)。商店需要组合k类不同糖果打包成礼盒出售。礼盒的甜蜜度是礼盒中任意两种糖果价格绝对差的最小值。问题:求满足打包要求的礼盒的最大甜蜜度。【输入】第1行:两个用空格隔开的数字n和k。第2行:n个整数,表示每种糖果的价格。【输出】输出只有一行,即满足打包要求的礼盒的最大甜蜜度。【输入样例】6 313 5 1 8 21 2【输出样例】8思路:这是二分答案找最大值的问题!· 定义check()函数检查在最大甜蜜度为x的情况下,是否可以找到k类不同糖果,使得两两价格绝对差的最小值大于等于x;· 为了方便计算价格差,需要先对糖果按价格排序;· 最大甜蜜度x的范围:最小0,最大可以取最贵的糖果的价格。#includeiostreamfincludealgorithmusingnamespacestd;inta[100010];intn,k;// check()函数检查在最大甜宝度为x的情况下,是否可以找到k类不同糖果,// 使得两两价格绝对差最小值大于等于x// 需要先对价格排序boolCheck(intx){intfirsta[1];//4)-FPRFintcnt1;for(inti2;in;i)//价格差满足x,可以作为第二种糖打包if(a[i]firstx){cnt1;firsta[i];}returncntk;}//在[min,max]之间二分查找使 Check()成立的答案(最大值)intfind(intmin,intmax){intleftmin,rightmax;// MATintans;while(leftright){intmid(leftright)/2;if(Check(mid)){//条件成立,答案在右半区问leftmid1;ansmid;//记录可能的答案}else{// 条件不成立,答案在左半区问rightmid-1;}}// 最终答案在ans中returnans;}intmain(){cinnk;for(intil;in;i){cina[i];}// 先排序(升序)sort(a1,an1);// 二分查找 0~max(a)coutfind(0,a[n]);return0;}【注意】二分查找前需要先对价格排序
