二分 一刀切两段

二分笔记

二分模版

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,a[N];
 //  int x = lower_bound(a+1, a+1+n, x) - a; // >= x 的第一个元素位置 
 //  int x = upper_bound(a+1, a+1+n, x) - a; // > x 的第一个元素位置
// 二分左边界
int left(int l,int r,int x){
	int ans=l;
	while(l<=r){
		int mid = l+r >> 1;
		if(a[mid] >= x) r=mid-1, ans=mid; 
		else l=mid+1;
	}
	if(a[ans] != x) ans=-1;
	return ans;
}
// 二分右边界
int right(int l,int r,int x){
	int ans=l;
	while(l<=r){
		int mid = l+r >> 1;
		if(a[mid] <= x) l=mid+1, ans=mid; 
		else r=mid-1;
	}
	if(a[ans] != x) ans=-1;
	return ans;
}
int main(){
	scanf("%d%d", &n, &m);	int x;
	for(int i=1; i<=n; i++) scanf("%d", &a[i]);
	while(m--){
		scanf("%d", &x);
		printf("%d ", right(1,n,x));
	}
	return 0;
}

905

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