二分法60分求助
查看原帖
二分法60分求助
754021
fish_love_cat楼主2022/12/31 12:44

RTRT

#include<bits/stdc++.h>
using namespace std;
int l,n,m,a[1000005];
bool pd(int b){
	int k=0,s=0;
	for(int i=0;i<=n;i++){
		if(a[i]-a[s]<b){
			k++;
		}else{
			s=i;
		}
	}
	if(k<=m){
		return true;
	}else{
		return false;
	}
	
}
int erfen(int left,int right){
	int sum;
	while(left<=right){
		int mid=(left+right)/2;
		if(pd(mid)){
			sum=mid;
			left=mid+1;
		}else{
			right=mid-1;
		}
	}
	return sum;
}
int main(){
	cin>>l>>n>>m;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	a[n]=l;
	cout<<erfen(0,l);
	return 0;
}
2022/12/31 12:44
加载中...