csp信奥赛C高频考点专项训练之贪心算法 --【贪心与二分判定】[NOIP 2015 提高组] 跳石头题目描述一年一度的“跳石头”比赛又要开始了这项比赛将在一条笔直的河道中进行河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间有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。思路分析题目要求在一条长度为L的线段上起点0和终点L固定中间有N块岩石位置递增最多移走M块岩石使得剩下的岩石含起点终点相邻距离的最小值最大。这是一个典型的“最小值最大化”问题可以用二分答案解决二分对象最短跳跃距离x。可行性判断对于给定的x判断能否通过移走不超过M块岩石使得所有相邻跳跃距离都 x。贪心策略从起点开始依次遍历中间岩石若当前岩石与上一块保留岩石的距离 x则移走当前岩石计数1否则保留并更新上一块位置。遍历完所有中间岩石后检查终点与最后保留岩石的距离若 x则需要移走最后保留的那块岩石计数1。最终判断移走总数 M是否成立。二分边界下界1最小可能距离上界L最大可能距离。复杂度O(N log L)在N5e4, L1e9范围内可行。代码实现#includebits/stdc.husingnamespacestd;intL,n,m,a[50005];//a存岩石位置boolck(intx){//检查最短距离x是否可行intcnt0,lst0;//移走数量上一块保留岩石位置for(inti1;in;i){if(a[i]-lstx)cnt;//距离不够移走当前岩石elselsta[i];//距离足够保留并更新}if(L-lstx)cnt;//最后一跳不够移走最后保留的岩石returncntm;}intmain(){scanf(%d%d%d,L,n,m);for(inti1;in;i)scanf(%d,a[i]);intl1,rL,ans0;while(lr){intmid(lr)1;if(ck(mid))ansmid,lmid1;//可行尝试更大elsermid-1;}printf(%d\n,ans);return0;}功能分析输入处理读取L, N, M和N块岩石位置。二分搜索在[1, L]区间内二分查找最大的可行最短距离。可行性检查贪心模拟跳跃过程每次尝试保留岩石不满足距离就移走。最后单独处理终点确保最后一跳也满足条件。输出最大化的最短跳跃距离。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整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信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新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;}