csp信奥赛C++高频考点专项训练：【二分答案】案例5：进击的奶牛

csp信奥赛C高频考点专项训练【二分答案】案例5进击的奶牛题目描述Farmer John 建造了一个有N NN2 ≤ N ≤ 10 5 2 \leq N \leq 10 ^ 52≤N≤105) 个隔间的牛棚这些隔间分布在一条直线上坐标是x 1 , x 2 , ⋯ , x N x _ 1, x _ 2, \cdots, x _ Nx1​,x2​,⋯,xN​0 ≤ x i ≤ 10 9 0 \leq x _ i \leq 10 ^ 90≤xi​≤109。他的C CC2 ≤ C ≤ N 2 \leq C \leq N2≤C≤N头牛不满于隔间的位置分布它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗Farmer John 想把这些牛安置在指定的隔间所有牛中相邻两头的最近距离越大越好。那么这个最大的最近距离是多少呢输入格式第1 11行两个用空格隔开的数字N NN和C CC。第2 ∼ N 1 2 \sim N12∼N1行每行一个整数表示每个隔间的坐标。输出格式输出只有一行即相邻两头牛最大的最近距离。输入输出样例 1输入 15 3 1 2 8 4 9输出 13AC代码#includebits/stdc.husingnamespacestd;constintN1e510;// 最大牛栏数量intn,c,a[N],ma,ans;// n:牛栏总数c:牛的数量a[]:牛栏位置数组ma:最大允许跳过的牛栏数ans:最终答案// 检查是否可以将c头牛以最小间隔x放置boolcheck(intx){intnowa[1];// 记录已放牛的位置intcnt1;// 已放奶牛数for(inti2;in;i){// 遍历后续牛栏if(a[i]nowx){// 当前牛棚可以放奶牛cnt;nowa[i];// 更新now的位置}}returncntc;// 返回是否能放得下c头牛}intmain(){cinnc;for(inti1;in;i)cina[i];sort(a1,an1);// 按位置排序牛栏// 二分查找最大可行解intl1;// 最小可能间隔intra[n]-a[1];// 最大可能间隔首尾距离while(lr){intmid(lr)/2;if(check(mid)){// 当前mid可行尝试更大的值ansmid;lmid1;}else{// 当前mid不可行减小最大值rmid-1;}}coutans;// 输出答案return0;}功能分析问题目标在n个有序牛栏中放置c头牛使得相邻牛之间的最小间隔最大化。这是典型的二分答案问题。核心逻辑排序预处理将牛栏位置排序便于计算间隔。二分框架在可能的最小间隔范围[1, 最大首尾距离]内二分搜索。验证函数check(x)判断是否能以最小间隔x放置c头牛。now变量记录已放牛的位置。cnt变量统计以x为最小间隔最多能放几头牛。判断条件如果cntc则放得下否则放不下。终止条件跳过的栏数超过mama n - c即最多允许跳过的栏数时返回false。复杂度时间复杂度排序复杂度为O(n log n)二分过程为O(log D)D为最大间隔每次check为O(n)总复杂度为O(n log n n log D)适用于n ≤ 1e5。空间复杂度O(n)存储牛栏位置。关键点边界处理首栏必须放置保证至少放置一头牛。完整信奥赛C普及组CSP-J一等奖通关刷题题单及题解请关注专栏https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}