题意：

n头牛，第i头坐标为xi，将它们分成c组，要求相邻两组最小距离最大。n≤100000。

题解：

二分最小距离。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 100010 7 using namespace std; 8  9 inline int read(){10     char ch=getchar(); int f=1,x=0;11     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}12     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();13     return f*x;14 }15 int n,c,x[maxn],l,r,ans;16 bool check(int a){17     int j=c-1,k=x[1]; inc(i,2,n){
   if(x[i]-k>=a)k=x[i],j--; if(!j)return 1;} return 0;18 }19 int main(){20     n=read(); c=read(); inc(i,1,n)x[i]=read(); sort(x+1,x+n+1); l=1; r=1000000000;21     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;22     return 0;23 }
        
       
      
     

 

20160929