C++跳石头

一、题目要求

1、编程实现

一年一度的“跳石头”比赛又要开始了这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有块岩石(不含起点和终点的岩石)。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走块岩石(不能移走起点和终点的岩石)

2、输入输出

输入描述：第一行包含三个整数L，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证L>1 目 NM≥0。
接下来 N 行，每行一个整数，第 i 行的整数 Di；(0<Di<L)， 表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出描述：只有一行，一个整数，即最短跳跃距离的最大值

输入样例：

25 5 2
2
11
14
17
21

输出样例：

4

数据要求：

• 对于 20%的数据，0≤M≤N≤10
• 对于 50%的数据，0≤M≤N≤100
• 对于 100%的数据，0≤M≤N≤50000,1≤L≤10^9

二、样例分析

由样例数据得到：组委会最多会搬走两块石头

1. 假如一块石头都不搬走，选手们的最短跳跃距离为2
2. 假如搬走一块石头，则搬走位置 2 的岩石，最短跳跃距离变为3
3. 假如搬走两块石头，再搬走位置 14 的岩石，最短跳跃距离变为 4;
4. 即最短跳跃距离的最大值为 4

三、算法分析

1. 有的小朋友可能会想到是不是可以使用排列组合的方式，从N块石头中取走M块，这个会出现超时
2. 还有的小朋友在碰到这题的时候可能会想着使用枚举的方式，依次遍历每一个石头找到他们最短的距离，然后从最短距离开始移除，当移除的石头数刚好等于指定的石头数然后输出；这种思路是可以的，只是由于数据量偏大，相对而言会较为耗时
3. 其实这题是比较典型的二分答案算法涉及的内容，题目已经告知石头是从小到大的顺序给出的，也就意味着数据是单调递增的，所以可以使用二分法枚举范围内的值，这样大大缩短了枚举的范围
4. 利用二分法确定每一次的最短跳跃距离，根据最短跳跃距离去搬走石头
5. 再根据最终搬走石头的数量来确定接下来是增大还是减小最短跳跃距离
6. 直到搬走的石头数量是指定的数值，同时距离最大

四、程序编写

#include<bits/stdc++.h>
using 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<=n;i++)
		cin >> stone[i];


	stone[n+1] = l;
	int left = 1,right = l;
	while(left <= right)
	{
		int mid = (left + right) / 2;
		int count = move(mid,n);
		if(count > m)	//石头超过规定石头缩小最短距离
			right = mid - 1;
		else		//石头少于规定石头加大最短距离
		{
			left = mid + 1;
			res = max(res,mid);
		}
	}
	cout << res << endl;
}


int move(const int mid,const int n)
{
	int count = 0,start = 1,next = 0;
	while(start <= n)
	{
		//如果start位置石头到next位置石头距离
		//小于最短距离移走next石头
		if(stone[start] - stone[next] < mid)
			count++;
		else
			next = start;
		start++;
	}
	//还要比较最后一块石头到终点距离是否满足
	if(next==n && stone[n+1]-stone[next]<mid)
		count++;
	return count;
}

四、运行结果

25 5 2
2
11
14
17
21


4

五、考点分析

难度级别：难，这题相对而言有一定难度，具体主要考察如下：

1. 分析题目，找到解题思路
2. 充分掌握数组和函数的定义及使用
3. 掌握二分答案算法的原理和使用
4. 分析出什么时候需要减少最短距离，什么时候需要增加最短距离
5. 学会输入流对象cin的使用，从键盘读入相应的数据
6. 学会while循环的使用，在不确定循环次数的时候推荐使用学会
7. 掌握输出流对象cout的使用，与流插入运算符 << 结合使用将对象输出到终端显示
8. 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路
9. 充分掌握数组定义和使用、分支语句、循环语句、函数和二分答案算法的应用

PS：方式方法有多种，小朋友们只要能够达到题目要求即可！