题解 | #愤怒的牛#

这道题的答案不能直接推出来，要靠试出来，还是最小值最大问题，我们一般使用二分，这道题就是典型的二分例题。

我们先把输入的 xi 排序，得到牛之间距离可能的最大值 xn，使用二分验证 1~xn 间的数是否可行

写一个子程序 check，验证数据（具体见代码注释），然后要取的是最大的 T 值。

AC code：

#include<bits/stdc++.h>
using namespace std;
int n, m, a[100001], low = 1, high, ans;
bool check(int x)//验证数据
{
    int l = a[1], cnt = 1;
    for(int i = 2;i <= n;i++)
    {
        if(a[i] - l >= x)//判断是否每两头牛之间的距离都大于最小值
        {
            l = a[i];
            cnt++;//记录多少头牛
        }
        if(cnt >= m)//够了
            return true;
    }
    return false;
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        cin >>a[i];
    }
    sort(a+1, a+n+1);
    high = a[n];//取最大值
    while(low <= high)
    {
        int mid = (low+high)/2;//二分
        if(check(mid))
        {
            low = mid+1;//最低边界升高
            ans = mid;//记录可行的答案
        }
        else
            high = mid-1;//最高边界降低
    }
    cout << ans;
}

-----END