这个题第二个数据是个坑,但是给我提了个醒

我们定义,l,r的时候可以比右边界多一,因为l<r,r是取不到的,而第二个数据的答案就是L,我一开始定义的r=L,结果答案总是差1,所以我把r=L+1,一开就过了.

#include<iostream>
using namespace std;
const int N1 = 1e5 + 5;
int L, N, M;
int a[N1];
bool check(int x) {
	int cnt = 0, now = 0;//now表示当前位置
	for (int i = 1; i <= N; ++i) {
		if (a[i] - now < x)cnt++;
		else now = a[i];
	}
	return cnt <= M;
}
int main() {
	scanf("%d%d%d", &L, &N, &M);
	for (int i = 1; i <= N; ++i)scanf("%d", &a[i]);
	int l = 0, r = L + 1, mid;//这里的r不能开成L,只能是L+1
	while (l < r) {
		mid = (l + r) >> 1;
		if (check(mid)) l = mid + 1;
		else r = mid;
	}
	printf("%d\n", r - 1);
	return 0;
}

关于二分的一点心得： 二分分出来的大多时候都是答案，所以我们要按照这个思路去找 比如这题，一开始我上来就想对石头二分，当然我们知道这是不 可能对的，二分需要check，按石头二分显然难以找到check。 后来看了下别人的代码，发现二分的就是答案，即距离x。所以拿 到一道二分题可以先看看答案是啥，凭着这个思路去找check，就 很简单了。（会不会大佬早就知道了，只有我现在才发现）

#include<iostream>
using namespace std;

int stone[50007];
int n,m,l;

int check(int x){
	int cns=0;
	int now=0;
	for(int i=1;i<=n;i++){
		if(stone[i]-stone[now]<x){
			cns++;
			if(cns>m){
				return false;
			}
		}
		else now=i;
	}
	return true;
}

int search(int l,int r){
	int mid;
	while(l<=r){
		mid=(l+r+1)>>1;
		if(!check(mid))r=mid-1;
		else l=mid+1;
	}
	return l-1;
}


int main(){
	cin>>l>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>stone[i];
	}
	cout<<search(0,l);
	return 0;
}

打卡

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int w[N];
int main(){
	long long l,n,m,maxx=0;
	cin>>l>>n>>m;
	for(int i=0;i<n;i++){
		cin>>w[i];
	}
	w[n]=l;
	long long left=1,right=l;
	while(left+1<right){
		int mid=left+right>>1;
		int ans=0,now=0;
		for(int i=0;i<=n;i++){
			if(w[i]-now>=mid) now=w[i];
			else{
				ans++;
			}
		}
		if(ans<=m) left=mid;
		else right=mid;
	}
	if(right==l) cout<<l;
	else cout<<right-1;
	return 0;
}