7-6 愤怒的牛 (25 分)

心已赠人 2023-10-11 16:24 20阅读 0赞

7-6 愤怒的牛 (25 分)

农夫约翰建造了一座有n间牛舍的小屋，牛舍排在一条直线上，第i间牛舍在xi的位置，但是约翰的m头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？

#### 输入格式: ####

第一行用空格分隔的两个整数n和m，n，m<=105；

第二行为n个用空格隔开的整数，表示位置xi。xi<MAXINT

#### 输出格式: ####

输出仅一个整数，表示最大的最小距离值。

#### 输入样例: ####

5 3
    1 2 8 4 9

#### 输出样例: ####

#include <bits/stdc++.h>
    using namespace std;
    int a[100010];
    int l, r;
    int n,c;
    
    /*bool juge(int m)//判断距离m是否可以 
    {
        int s = 0, last = 1;//记录上一个 
        for (int i = 2; i <= n; i++)//依次枚举每个牛栏 
        {
            if (a[i] - a[last]<m)s++;//若此距离不满足当前答案，那么需要的牛栏数+1，即把当前牛放到下一个牛栏 
            else last = i;//否则就更新上一次的牛栏位置 ，即上一头牛放的位置 
            if (s>n - c) return false;//若需要牛栏数大于最大牛栏数，此答案不可行 
        }
        return true;
    }*/
    
    bool juge(int m)              
    {
        int ans = 1, last = 1;           //因为第一个牛一定要占据第一个隔间（这样能使本题的答案最优），所以ans初始化为1
        for (int i = 2; i <=n; i++)
        {
            if (a[i] - a[last] >= m)
            {
                ans++;           //如果比最近距离要大的话，那么该隔间就放牛   
                last = i;                                               
            }
        }
        if (ans >= c)return true;          //如果所选取的隔间数量>=c，则说明枚举的最近距离成立，但是不够大，所以return true,继续枚举更大的距离
        return false;
    }
    
    int main()
    {
        cin >> n >> c;
        for (int i = 1; i <=n; i++)cin >> a[i];
        l = 1; r = a[n] - a[1];           //右边界为n个隔间的总长度，最近距离一定小于等于这个数值
        sort(a + 1, a + 1 + n);
        while (l <=r)
        {
            int mid = (l + r)/2;
            if (juge(mid))l = mid+1;       //如果当前枚举的最近距离符合，那么就让l=mid,看更大的距离是否也符合（因为要求最大的最近距离）
            else
                r = mid-1;
        }
        cout << r<< endl;    //由于最后l<=r的时候还会运行一次，会让l-1(如果答案正确的话)，所以应该输出的是r
        return 0;
    }