#include<bits/stdc++.h>
using namespace std;
int a[100001];
int n,m;
bool search(int dis)
{
	int ans=1;int pre=1;
	while(ans<m)
	{
		int low=lower_bound(a+1,a+1+n,a[pre]+dis)-a;
		if(low>=n+1)
		{
			if(ans<m)
			return false;
			else if(ans>=m) 
			return true;
		}
		else if(low<=n)
		{
			ans++;
			pre=low;
		}
	}
	return true;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	int pre;int left=1;int right=a[n];
	while(left+1<right)
	{
		int mid=(left+right)/2;
		bool p=search(mid);
		if(p==false)
		{
			right=mid;
		}
		else
		left=mid;
	}
	cout<<left;
	return 0;
}

考虑二分答案（这好像跟楼上是两种思路）

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],d;
int c[100005];
bool check(int k){//验证此答案是否可行
	int cnt=1,tmp=0;
	for(int i=2;i<=n;i++){
		tmp+=c[i];
		if(tmp>=k) cnt++,tmp=0; 
	}
	if(cnt>=m) return true;
	else return false;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	for(int i=2;i<=n;i++){
		c[i]=a[i]-a[i-1];//差分
		d=max(d,c[i]);//二分上界
	}
	int l=0,r=d*2;
	int mid;
	while(l+1<r){//二分答案
		mid=(l+r)>>1;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%d",l);
	return 0;
} 

其实是贪心

找 距离 max 尽可能的让牛在不挤的情况下往前待

正常是for 1 to f[n]/m+1 程序如下

时间复杂度O(n)=n*f[n]/m 80分代码

#include<bits/stdc++.h>
using namespace std;
int f[100005],now=-2147483647;
int main()
{
	int n,m,k;
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
	scanf("%d",&f[i]);
	
	sort(f+1,f+n+1);
	for(int j=1;j<=n;j++)
		{
	//		cout<<f[j];
		}
	k=m;
	for(int i=1;i<=f[n]/m+1;i++)
	{
		k=m;
		now=-2147483647;
		for(int j=1;j<=n;j++)
		{
			if(now+i<=f[j]) now=f[j],k--;
			if(k==0) break;
		}
		if(k>0)
		 {
		 	cout<<i-1;
		 	return 0;
		 }
	}
//	cout<<f[n]/m;
 } 

会超时，因为单调性所以要用二分距离来优化、

left=1 right=f[n]/n(max average) 分分分

以下为AC代码

#include<bits/stdc++.h>
using namespace std;
int f[100005],now=-2147483647;
int main()
{
	int n,m,k;
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
	scanf("%d",&f[i]);
	
	sort(f+1,f+n+1);
	k=m;
	int left=1,right=f[n]/m+1,mid=(left+right)/2;
	bool pd=true;
	while(left<right)
	{
		mid=(left+right)/2;
		k=m;
		now=-2147483647;
		for(int j=1;j<=n;j++)
		{
			if(now+mid<=f[j]) now=f[j],k--;
			if(k==0) break;
		}
		if(k>0)
		 {
			 pd=false;	
		 }
		 else pd=true;
		 
		 if(pd==false) right=mid;
		 else left=mid+1;
	}
	cout<<right-1;

 } 

这是二分题 题意： 给 n 个牛棚，m头牛，要求把 m 头牛放入 m 个牛棚里，并使得距离最小得两个牛棚之间得距离尽量大。

做题的时候一直在思考怎么通过排序牛棚的坐标来求。这个思路是有点问题的。

还是没有想到根本上去。

我们需要求的是大于某个最小距离的 m 个牛棚。

我们可以用二分的方法来求这个距离： 求一个中点距离，从前到后判断两个牛棚间隔大于这个中点距离的牛棚数。

如果大于这个距离的牛棚数大于牛的数量，就增大两牛棚的距离，反之缩小距离。