[USACO16JAN] Angry Cows S
题目描述
Bessie 设计了一款新游戏:*Angry Cows*。在这个游戏中,玩家发射奶牛,每头奶牛落地时引爆一定范围内的干草。游戏的目标是使用一组奶牛引爆所有干草。
$N$ 捆干草排列在数轴上的不同位置。第 $i$ 捆干草的的位置为 $x_i$。如果一个威力为 $R$ 的奶牛在 $x$ 位置落地,她将引爆 $[x-R,x+R]$ 范围内的所有干草。
你现在可以发射 $K$ 头奶牛,每头奶牛的威力都是 $R$,现在你需要确定 $R$ 的最小值,使得用 $K$ 头奶牛可以引爆所有干草。
输入输出格式
输入格式
第一行两个整数 $N,K$($1 \leq N \leq 5 \times 10^4$,$1 \leq K \leq 10$)。
接下来 $N$ 行,第 $i$ 行一个整数 $x_i$($0 \leq x_i \leq 10^9$)。
输出格式
输出一个整数,即 $R$ 的最小值。
输入输出样例
输入样例 #1
7 2
20
25
18
8
10
3
1
输出样例 #1
5