P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows（洛谷题面）

题目

题目描述：

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

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

输入格式：

第一行用空格分隔的两个整数 nn 和 mm；

下面 nn 行为 nn 个用空格隔开的整数，表示位置 xix_i。

输出格式：

一行一个整数，表示最大的最小距离值。

数据范围与说明：

【样例解析】把牛放在 11，44，88 这三个位置，距离是 33。容易证明最小距离已经最大。

【数据范围】对于 100%100\% 的数据，2≤n≤1052 \le n \le 10^5，0≤xi≤1090 \le x_i \le 10^9，2≤m≤n2 \le m \le n。不保证 xx 数组单调递增。

输入输出样例 #1

输入：

1
2
3
4
5
6
5 3
1
2
8
4
9

输出：

1
3

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
int n,c,a[100005];
int ans;
bool check(int mid){
    int cnt=1,p=0;
    for(int i=1;i<n;i++){
        if(a[i]-a[p]>=mid){
            cnt++;
            p=i;
        }
    }
    if(cnt>=c)  return true;
    else    return false;
}
int main(){
    scanf("%d %d",&n,&c);
    for(int i=0;i<n;i++)    scanf("%d",&a[i]);
    sort(a,a+n);
    int left=0,right=a[n-1]-a[0];
    while(left<=right){
        int mid=left+(right-left)/2;
        if(check(mid)){
            ans=mid;
            left=mid+1;
        }else{
            right=mid-1;
        }
    }
    cout<<ans;
    return 0;
}