摘要：一年一度的“跳石头”比赛又要开始了这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有块岩石(不含起点和终点的岩石)。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点
一年一度的“跳石头”比赛又要开始了这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有块岩石(不含起点和终点的岩石)。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走块岩石(不能移走起点和终点的岩石)
输入描述：第一行包含三个整数L，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证L>1 目 NM≥0。
接下来 N 行，每行一个整数，第 i 行的整数 Di；(0
输出描述：只有一行，一个整数，即最短跳跃距离的最大值
输入样例：
三、算法分析
有的小朋友可能会想到是不是可以使用排列组合的方式，从N块石头中取走M块，这个会出现超时还有的小朋友在碰到这题的时候可能会想着使用枚举的方式，依次遍历每一个石头找到他们最短的距离，然后从最短距离开始移除，当移除的石头数刚好等于指定的石头数然后输出；这种思路是可以的，只是由于数据量偏大，相对而言会较为耗时其实这题是比较典型的二分答案算法涉及的内容，题目已经告知石头是从小到大的顺序给出的，也就意味着数据是单调递增的，所以可以使用二分法枚举范围内的值，这样大大缩短了枚举的范围利用二分法确定每一次的最短跳跃距离，根据最短跳跃距离去搬走石头再根据最终搬走石头的数量来确定接下来是增大还是减小最短跳跃距离直到搬走的石头数量是指定的数值，同时距离最大#includeusing namespace std;const int N = 50010;int stone[N];int move(const int,const int);int main{ int l,n,m,res = 0; cin >> l >> n >> m; for(int i=1;i> stone[i]; stone[n+1] = l; int left = 1,right = l; while(left m) //石头超过规定石头缩小最短距离 right = mid - 1; else //石头少于规定石头加大最短距离 { left = mid + 1; res = max(res,mid); } } cout 分析题目，找到解题思路充分掌握数组和函数的定义及使用掌握二分答案算法的原理和使用分析出什么时候需要减少最短距离，什么时候需要增加最短距离学会输入流对象cin的使用，从键盘读入相应的数据学会while循环的使用，在不确定循环次数的时候推荐使用学会掌握输出流对象cout的使用，与流插入运算符 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路充分掌握数组定义和使用、分支语句、循环语句、函数和二分答案算法的应用PS：方式方法有多种，小朋友们只要能够达到题目要求即可！
来源：弘德教育
免责声明：本站系转载，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与本站联系，我们将在第一时间删除内容!
