P6174 [USACO16JAN]Angry Cows S

题意：Bessie 设计了一款新游戏：Angry Cows。在这个游戏中，玩家发射奶牛，每头奶牛落地时引爆一定范围内的干草。游戏的目标是使用一组奶牛引爆所有干草。

N 捆干草排列在数轴上的不同位置。第 i 捆干草的的位置为 x[i]。如果一个威力为 R 的奶牛在 x 位置落地，她将引爆 [x−R,x+R] 范围内的所有干草。

你现在可以发射 K 头奶牛，每头奶牛的威力都是 R，现在你需要确定 R 的最小值，使得用 K 头奶牛可以引爆所有干草。
题解：
这种最小值，一般来说就是二分答案了，重点还是在于二分答案中的check函数怎么写，这里的话，check函数中有一种贪心的思想在里面，即，从前往后遍历点，在能占到这个点的情况下，尽量把多余的范围往后延伸，因为前面的甘草已经被引爆了，所以把多余的范围尽量往后延伸，这样才会尽可能多的引爆后面的甘草。
代码：

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define Accepted 0
#define AK main()
#define I_can signed
using namespace std;
const int maxn =1e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int n,k;
int a[maxn];
//map<int> mp;

bool check(int x){
    int steps=0,cnt=0;
    for(int i=0;i<n;i++){
        if(steps<a[i]){
            cnt++;
            steps=a[i]+x*2;
        }
    }
    return cnt<=k;

}

I_can AK{
    ios::sync_with_stdio(false);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    int ans=0,l=0,r=1e9+10;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
        //cout<<mid<<endl;
    }
    cout<<ans+1<<endl;

    return Accepted;
}