#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
struct node{
	int last,len;
}b[maxn];
int a[maxn],n,cnt,ans;
bool check(int x){
	cnt=0;
	int now=0;
	for(int i=1;i<=n;i++){
		bool flag=0;
		now=0;
		for(int j=1;j<=cnt;j++)
			if(a[i]==b[j].last+1&&b[j].len<b[now].len){
				flag=1,now=j;
			}
		if(flag)
			b[now].last=a[i],b[now].len++;
		else{
			cnt++;
			b[cnt].len=1,b[cnt].last=a[i];
		}
	}
	for(int i=1;i<=cnt;i++)
		if(b[i].len<x)
			return false;
	return true;
}
int main(){
	b[0].len=0x3f3f3f3f;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	int l=1,r=n;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			ans=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	printf("%d",ans);
	return 0;
}

这种做法如果输入一个公差大于等于2的等差数列每一次check都会被卡成n*n

求助有没有check是O(n) or O(nlogn)的二分答案做法

或者复杂度能过的其他二分答案做法