[牛客] [NOIP2015]跳石头

前言

$tag:$二分二分答案
题意 :

思路 :
因为题目所求的是 最短的最大 ,很标准的一个二分询问方法

因此我们可以考虑二分最短距离,那么我们怎么check呢

很简单,显然对于现在的需要判断的 x，如果两个石头的差小于x的时候 , 我们肯定是要将其移走的

所以我们只需要判断移走的数量和m的关系即可

当然移走的状态我们可以通过last进行转移
code :

int L,n,m;

int a[N];
int i,j;
int b[N];

bool check(int x){
    
	int cnt = 0;
	int last = 0 ;
	
	Fup(i,1,n+1){
    
	 	if(a[i] - last < x) cnt++;
	 	else last = a[i];
	 	if(cnt > m) return false;
	 	
	}
	return true;
}
void solve(){
    
	// cin>>L>>N>>M;
	cin>>L>>n>>m;
	Fup(i,1,n) cin>>a[i];
	
	a[n+1] = L;
	
	
	int l = 0 , r =  L;
	
	
	
	//cout<<ans<<endl;
	
	
	while(l<=r){
    
		int mid = (l+r)>>1;
		if(check(mid)){
     
			l = mid+1;
		}
		else r = mid - 1;
	}
	
	cout<<((l+r)>>1)<<endl;
	
	
}
signed main(){
    
	//int t;cin>>t;while(t--)
    solve();
    return 0 ;
}