#G. 小熊炸弹

Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

战码设计了一个新型的破坏游戏：愤怒小熊。游戏的前提是玩家用弹弓将小熊射入一维场景中，场景由一条数字线上的一组蜂蜜罐组成。每只小熊着陆时产生足够的力量，使附近的蜂蜜罐爆炸。

游戏目标是使用一组小熊爆破场景中的所有蜂蜜罐。

数字线上有 N 个蜂蜜罐，位于不同的整数位置 x1,x2,…,xN 。

如果一只小熊以 R 的力量降落在位置 x，这将产生一个“半径 R”的爆炸，摧毁范围 [x−R,x+R] 内的所有蜂蜜罐。

共有 K 只小熊可以射击，每只小熊具有相同的力量 R。请确定 R 的最小整数值，使得可以最多使用 K 只小熊破坏场景中的每个蜂蜜罐。

输入的第一行包含 N 和 K 。

其余 N 整数 x1,x2,…,xN 。

请输出每只小熊必须发射的最小力量 R，以破坏所有蜂蜜罐。