其实是贪心

找 距离 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;

 }