跳石头|题解

前置知识：

二分查找

思路：

最寻常的思路就是暴力 $dfs$ 每一种情况，显然看数据可知会超时。这时可以枚举$最短跳跃距离的最大值$，每次判断是否合法，显然比 $dfs$ 做法快了很多，时间复杂度为$O(NL)$，可是还会超时，所以考虑将枚举$最短跳跃距离的最大值$这个时间缩短，所以考虑配合二分查找使用，同样判断是否合法，若合法就尝试更大的值，若不合法就换用更小的值，此算法就叫$二分答案$，十分高效快速。

时间复杂度：

$O(N*logL)$，通过此题完全没有问题。

代码：

二分答案模板题，作出已给出详细思路，这里给出判断是否合法函数的代码，其余代码自己完成。

bool check(int d){
	int time=0;
	int last=0;
	for(int i=1;i<=n;i++){
		if(a[i]-last<d) time++;
		else last=a[i];
	}
	return time<=m;
}