Angry Cows

题目描述

奶牛 Bessie 设计了一款她认为会成为下一款爆款的视频游戏：“Angry Cows”。其设定（她相信完全原创）是：玩家用弹弓把一头奶牛射入一维场景，场景中有若干个位于数轴不同位置的干草堆；奶牛落地时有足够的力量引爆落点附近的干草堆，而这些爆炸又可能引发连锁反应，使更多干草堆爆炸。目标是用一头奶牛引发连锁反应，炸掉所有干草堆。

数轴上有 $N$ 个干草堆，位于互不相同的整数位置 $x_1, x_2, \ldots, x_N$。如果以能量 $R$ 发射一头奶牛，使其落在位置 $x$，将产生一个“半径为 $R$”的爆炸范围，覆盖区间 $x-R \ldots x+R$ 内的所有干草堆。这些干草堆随后也会爆炸（同时发生），每个爆炸的半径为 $R-1$。任何尚未爆炸且被这些爆炸波及的干草堆将再次全部爆炸（同时发生），其爆炸半径为 $R-2$，以此类推。

请你确定最小的能量 $R$，使得只发射一头奶牛，并让其落在某个合适的位置，就能通过后续爆炸引爆场景中的每一个干草堆。

输入格式

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

输出格式

输出奶牛必须以的最小能量 $R$，才能引爆所有干草堆。答案需要四舍五入，并且恰好输出 1 位小数。

5
8
10
3
11
1

3

提示

在该例中，以能量 3 将奶牛发射到例如位置 5，会立即引爆位置 3 和 8 的干草堆。它们随后（同时）以爆炸半径 2 爆炸，覆盖位置 1 和 10 的干草堆；接着这些干草堆（同时）以爆炸半径 1 爆炸，覆盖最后一个位于 11 的干草堆；它最终以爆炸半径 0 爆炸。

题目来源：Brian Dean

标签: USACO|2016|Gold

来源

USACO|2016|Gold