Angry Cows

题目描述

奶牛 Bessie 设计了一款她认为会成为下一个热门的视频游戏：“Angry Cows”。其设定（她相信完全原创）是：玩家用弹弓把奶牛射入一个一维场景，场景由数轴上若干位置的干草堆组成。每头奶牛落地时会以足够的力量引爆其落点附近的干草堆。目标是使用给定数量的奶牛引爆所有干草堆。

数轴上有 $N$ 个干草堆，位于互不相同的整数位置 $x_1, x_2, \ldots, x_N$。如果以威力 $R$ 发射一头奶牛并使其落在位置 $x$，将产生“半径为 $R$”的爆炸，摧毁范围 $x-R \ldots x+R$ 内的所有干草堆。

现在有总共 $K$ 头奶牛可供发射，每头奶牛的威力均为 $R$。请确定最小的整数 $R$，使得可以使用这 $K$ 头奶牛引爆场景中的每一个干草堆。

输入格式

第一行输入包含 $N$（$1 \leq N \leq 50,000$）和 $K$（$1 \leq K \leq 10$）。接下来 $N$ 行每行包含一个整数 $x_1 \ldots x_N$（每个都在范围 $0 \ldots 1,000,000,000$）。

输出格式

请输出每头奶牛必须以多大的最小威力 $R$ 发射，才能引爆所有干草堆。

7 2
20
25
18
8
10
3
1

5

提示

题目来源：Brian Dean

标签: USACO|2016|Silver

来源

USACO|2016|Silver