题解：P2678 [NOIP2015 提高组] 跳石头

思路

一道二分题，此题的关键是一个 check 函数。

关键点（check）

先遍历所有岩石，如果当前岩石和上一块每一掉岩石的的距离小于 $mid$ （ $mid$ 是当前猜测的最小步数），就要移掉当前岩石，否则就要更新上一块未被一走的岩石的位置（也就是把上一块的位置是加 $1$ ）
判断要移走的是否不超过最多可以移掉的岩石数量。

时间复杂度为

\mathcal{O(n \log t)}

，可以通过。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int a[N];
int t,n,m;
bool check(int mid){
	int cnt=0,l=0;
	for(int i=1;i<=n+1;i++){
		if(a[i]-a[l]<mid) cnt++;
		else l=i;
	}
	return cnt<=m;
}
int main(){
	cin>>t>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	a[n+1]=t;
	int l=0,r=t;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l;
	return 0;
}

题解：P2678 [NOIP2015 提高组] 跳石头

文章操作

思路

关键点（check）

代码

相关推荐

评论

题解：P2678 [NOIP2015 提高组] 跳石头