洛谷P2678 跳石头 题解

来到华工已经半个星期，昨天听了acm的宣讲，然后想起来这道之前打算练的题还没有做，于是在窝工的图书馆尝试着做了一下。

题目链接：P2678 [NOIP2015 提高组] 跳石头 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

分析过程

这道题目要我们找最短跳跃距离的最大值，如果用搜索的话，在这个数据规模之下会超时，而且要求的答案是明显有一个范围的——一定在 \([1,L]\) 的范围里。那么我们可以用二分的思想去枚举出这个答案。既然我们要找的是最大值，那么如果枚举到的一个值是可行的，我们就应该继续往大了去找，也就是在右边的区间继续去找；如果我们枚举到的一个值是不可行的，那么比它大的就更不可行，我们就要在左边的区间去找。代码如下：

while(left<=right){
		int mid=(left+right)/2;
		if(ok(mid)){
			ans=mid;
			left=mid+1;//如果这个距离可以，就往更大试试
		}else{
			right=mid-1;//如果这个距离都不行，那更大肯定更不行，只能更小
		}
	}  

至于说答案判断函数，我们只需统计一共要移走多少个石头才能使某个值成为最短跳跃距离的最大值。一开始我写得不太好：

bool ok(int x){
	int cnt=0;
	for(int i=1;i<=n+1;++i){
		int last=i-1;
		while(del[last]==1) last--;
		if(stone[i]-stone[last]<x){
			del[i]=1;
			cnt++;
		} 
	}
	memset(del,0,sizeof(del));
	return cnt>m? false : true ;
}

其中stone存的是每个石头距离起点的距离，del表示这个石头是否被删除。这段代码最大的瑕疵还是我把cnt>m放在了最后判断，其实应该放在for循环里就判断（memset放在函数最开始），这样能节省时间。然后是del数组，其实也是没必要的，可以有更好的写法：

bool ok(int x){
	int cnt=0,last=0;
	for(int i=1;i<=n+1;++i){
		if(stone[i]-stone[last]<x) cnt++;
		else last=i;//石头i没有被拿走，那么下一次就是从i跳到i+1，也就是说下一次判断的前一个石头是i
		if(cnt>m) return false;
	}
	return true;
}

完整代码

#include <bits/stdc++.h>
using namespace std;
int l,n,m,stone[50002];
bool ok(int x){
	int cnt=0,last=0;
	for(int i=1;i<=n+1;++i){
		if(stone[i]-stone[last]<x) cnt++;
		else last=i;//石头i没有被拿走，那么下一次就是从i跳到i+1，也就是说下一次判断的前一个石头是i
		if(cnt>m) return false;
	}
	return true;
}
int main(){
	cin>>l>>n>>m;
	int left=1,right=l,ans=0;
	for(int i=1;i<=n;++i){
		cin>>stone[i];
	}
	stone[n+1]=l;
	while(left<=right){
		int mid=(left+right)/2;
		if(ok(mid)){
			ans=mid;
			left=mid+1;//如果这个距离可以，就往更大试试
		}else{
			right=mid-1;//如果这个距离都不行，那更大肯定更不行，只能更小
		}
	}
	cout<<ans;
	return 0;
}