题目描述

Description

奶牛Bessie设计了一个游戏：“愤怒的奶牛”。游戏的原型是：有一些可爆炸的草堆分布在一条数轴的某些坐标上，玩家用弹弓把一头奶牛发射到数轴上。奶牛砸到数轴上的冲击波会引发附近的草堆爆炸。游戏的目标是玩家用一些奶牛炸掉所有的草堆。
有N个草堆在数轴的不同位置，坐标为x1,x2,….,xn。如果玩家以能量R把奶牛发射到坐标x，就会引爆半径R及以内的的草堆，即坐标范围[x−R,x+R]的草堆都会燃爆。
现在有K头奶牛，每头奶牛的能量都是R，请计算如果要引爆所有的草堆，最小的R是多少？

Input

第一行：2个整数N(1≤N≤50,000)和K(1≤K≤10)。
下面有N行,每行一个整数：x1,x2,…,xn，范围在[0…1,000,000,000]。

Output

输出最小可能的R。

Sample Input

7 2
20
25
18
8
10
3
1

Sample Output

5

题目分析

二分+贪心check 注意:不一定将奶牛正好砸在草堆上

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int x[50010];
int check(int mid)
{
    int num=0;
    for(int i=1;i<=n;)  
    {
        num++;
        int tmp=x[i];
        while(i+1<=n&&x[i+1]-tmp<=mid*2) i++;
        i++;
    }
    return num;
}
int main()
{   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&x[i]);
    sort(x+1,x+n+1);
    int l=0,r=1000000000,mid,ans;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid)<=m) ans=mid,r=mid;
        else l=mid+1;
    }
    printf("%d",ans);
    return 0;
}