如何放牛

蔚落 2022-04-03 02:51 138阅读 0赞

###  ###

题目描述

农夫有n个牛栏，m头牛，然后要让你把m个牛都放进牛栏里，让两头牛之前的最大的最小距离

输入

输入n,m (1<=m<=n<=100000)

下面n行是牛栏的位置xi (0 <= xi <= 1,000,000,000)

输出

输出两头牛最大的最小距离

样例输入

5 3  
1  
2  
8  
4  
9

样例输出

提示

FJ可以将他的3头奶牛放在位置1,4和8的摊位上，最小距离为3.

大量输入数据，建议使用scanf。

##### 分析： #####

本题，在我一开始做的时候根本就没有思路。不过我唯一能肯定的就是最小的那个位置的牛栏一定是会放牛的。由此考虑下去，我可以假设第二头放的位置与第一头牛放的位置，之间的距离是(end-start)/2=distance。之后的每一条牛放的位置，与之之前的那头牛的位置的之间的距离一定是大于distance的。然后判断，在距离为distance的时候，能不能把牛全部放进去。如果能则distance的值赋给start。如果不能则将distance的值赋给end。由此不断循环判断。可得出正确的答案。  
不过，在放牛的时候，需要对牛的位置进行排序。又因为牛的位置的数量较多，所以需要用到快排。 在本代码中，我是直接让它执行100次的循环。不过时间超限，当改为30次成功AC。

#include"stdio.h"
    #include"string.h"
    
    long long Serch(long long x[],double Min_distance,double End_distance,long long N,long long M)
    {
        long long i,Min,j;
        //printf("Min_distance=%lf End_distance=%lf\n",Min_distance,End_distance);
        double Mid_distance=(Min_distance+End_distance)/2.0;
        //printf("Mid_distance=%lf\n",Mid_distance);
        j=0;
        for(i=1;i<N;i++)
        {
            if(x[j]+Mid_distance<=x[i])
                {M--;
                 j=i;//这里是保存上一条牛的位置的下标
                }
           if(M==1)
              break;
        }
        if(i==N)
            return 0;
    
    
        return 1;
    }
    //手写快排。
    void swap(long long x[],long long start,long long end)
    {
        long long t;
        t=x[start];
        x[start]=x[end];
        x[end]=t;
    }
    long long location(long long x[],long long start,long long end)
    {
        long long Key;
        long long T;
        Key=x[start];
        while(start<end)
        {
            while(start<end&&x[end]>=Key)
                end--;
            swap(x,start,end);
            while(start<end&&x[start]<=Key)
                start++;
            swap(x,start,end);
        }
        return start;
    }
    void Sort(long long x[],long long start,long long end)
    {
        long long local;
        if(start<end)
        {
            local=location(x,start,end);
            Sort(x,start,local-1);
            Sort(x,local+1,end);
        }
    }
    int main()
    {
        long long m,n;
        long long x[100001];
        long long i,j,k,count,mark,t;
        double Min_distance,End_distance;
        while(~scanf("%lld%lld",&n,&m))
        {   count=0;
            for(i=0;i<n;i++)
                {scanf("%lld",&x[i]);
                }
            Sort(x,0,n-1);
            End_distance=100000;
            Min_distance=0;
            while(count++<20)
            {
                mark=Serch(x,Min_distance,End_distance,n,m);
                if(mark==1)
                    Min_distance=(Min_distance+End_distance)/2.0;
                else
                    End_distance=(Min_distance+End_distance)/2.0;
    
    
            }
         printf("%0.0lf\n",(Min_distance+End_distance)/2.0);
        }
    }