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(0<Di<L)， 表示第i ii块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
一个整数，即最短跳跃距离的最大值。
输入输出样例 1
输入 1
25 5 2 2 11 14 17 21输出 1
4说明/提示
输入输出样例 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)，在N=5e4, L=1e9范围内可行。
代码实现
#include<bits/stdc++.h>usingnamespacestd;intL,n,m,a[50005];//a存岩石位置boolck(intx){//检查最短距离x是否可行intcnt=0,lst=0;//移走数量，上一块保留岩石位置for(inti=1;i<=n;++i){if(a[i]-lst<x)++cnt;//距离不够，移走当前岩石elselst=a[i];//距离足够，保留并更新}if(L-lst<x)++cnt;//最后一跳不够，移走最后保留的岩石returncnt<=m;}intmain(){scanf("%d%d%d",&L,&n,&m);for(inti=1;i<=n;++i)scanf("%d",&a[i]);intl=1,r=L,ans=0;while(l<=r){intmid=(l+r)>>1;if(ck(mid))ans=mid,l=mid+1;//可行，尝试更大elser=mid-1;}printf("%d\n",ans);return0;}功能分析
- 输入处理：读取
L, N, M和N块岩石位置。 - 二分搜索：在
[1, L]区间内二分查找最大的可行最短距离。 - 可行性检查：
- 贪心模拟跳跃过程，每次尝试保留岩石，不满足距离就移走。
- 最后单独处理终点，确保最后一跳也满足条件。
- 输出：最大化的最短跳跃距离。
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;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++标准模板库STL：
https://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 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
