csp信奥赛C++高频考点专项训练：【二分答案】案例4：跳石头

csp信奥赛C高频考点专项训练【二分答案】案例4跳石头题目描述一年一度的“跳石头”比赛又要开始了这项比赛将在一条笔直的河道中进行河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间有N NN块岩石不含起点和终点的岩石。在比赛过程中选手们将从起点出发每一步跳向相邻的岩石直至到达终点。为了提高比赛难度组委会计划移走一些岩石使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制组委会至多从起点和终点之间移走M MM块岩石不能移走起点和终点的岩石。输入格式第一行包含三个整数L , N , M L,N,ML,N,M分别表示起点到终点的距离起点和终点之间的岩石数以及组委会至多移走的岩石数。保证L ≥ 1 L \geq 1L≥1且N ≥ M ≥ 0 N \geq M \geq 0N≥M≥0。接下来N NN行每行一个整数第i ii行的整数D i ( 0 D i L ) D_i\,( 0 D_i L)Di​(0Di​L) 表示第i ii块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出且不会有两个岩石出现在同一个位置。输出格式一个整数即最短跳跃距离的最大值。输入输出样例 1输入 125 5 2 2 11 14 17 21输出 14说明/提示输入输出样例 1 说明将与起点距离为2 22和14 1414的两个岩石移走后最短的跳跃距离为4 44从与起点距离17 1717的岩石跳到距离21 2121的岩石或者从距离21 2121的岩石跳到终点。数据规模与约定对于20 % 20\%20%的数据0 ≤ M ≤ N ≤ 10 0 \le M \le N \le 100≤M≤N≤10。对于50 % 50\%50%的数据0 ≤ M ≤ N ≤ 100 0 \le M \le N \le 1000≤M≤N≤100。对于100 % 100\%100%的数据0 ≤ M ≤ N ≤ 50000 , 1 ≤ L ≤ 10 9 0 \le M \le N \le 50000,1 \le L \le 10^90≤M≤N≤50000,1≤L≤109。AC代码#includebits/stdc.husingnamespacestd;intL,N,M,a[50010],ans;// 检查函数判断是否可以在移除不超过M块岩石的情况下使所有跳跃距离至少为xboolcheck(intx){intlast0;// 上一个未被移除的岩石位置初始为起点0intcnt0;// 统计需要移除的岩石数量for(inti1;iN;i){if(a[i]-lastx){// 当前岩石与上一个未被移除的岩石距离不足x需移除当前岩石cnt;}else{// 距离足够保留当前岩石更新lastlasta[i];}}// 检查最后一个未被移除的岩石到终点的距离if(L-lastx)cnt;// 若不足x需移除最后一个岩石但终点不可移除故cnt增加returncntM;// 判断总移除数是否在允许范围内}intmain(){cinLNM;for(inti1;iN;i)cina[i];intl1,rL;// 二分范围最短距离可能的最大值范围[1, L]while(lr){intmid(lr)/2;if(check(mid)){// 当前mid可行尝试寻找更大的值ansmid;lmid1;}else{// 当前mid不可行减小范围rmid-1;}}coutans;return0;}功能分析问题目标在最多移除M块岩石的情况下最大化选手跳跃过程中的最短距离。二分答案通过二分法确定可能的最大最短距离x。对于每个x使用check函数验证是否可行。check函数逻辑遍历每块岩石若当前岩石与上一个保留岩石的距离小于x则移除当前岩石。遍历结束后检查最后保留的岩石到终点的距离是否小于x若是则需移除该岩石。统计总移除数是否不超过M若成立则x可行。二分边界初始范围为1到L确保覆盖所有可能值。最终答案通过调整左右边界确定。完整信奥赛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;}