G - 胆小的鲁鲁修
题目描述
深夜,鲁鲁修沿着一条点着 $n$ 盏灯笼,长为 $L$ 的直街走着。街道的起点为 $0$ ,终点为 $l$ ,第 $i$ 盏灯的位置为ai。每只灯笼点亮了街道上所有与它距离不超过 $d$ 的点,其中 $d$ 是一个正数。
鲁鲁修十分怕黑且非常节约,他想知道:要照亮整条街,灯笼的最小照明半径应该是多少?
输入格式
第一行包含两个整数 $n$ , $L$ ,分别表示灯笼的数量和街道的长度。
下一行包含 $n$ 个整数。多个灯笼可以位于同一点。灯笼可能被放置在街道的尽头。
输出格式
输出最小光半径 $d$ ,需要照亮整个街道。如果答案的绝对误差或相对误差不超过 1e-9,则认为答案是正确的。
样例 #1
样例输入 #1
7 15
15 5 3 7 9 14 0
样例输出 #1
2.5000000000
样例 #2
样例输入 #2
2 5
2 5
样例输出 #2
2.0000000000
思路: 我们知道,输入的灯笼位置是无序的,我们先对灯笼进行排序,先找出输入灯笼每两个之间距离的最大值,记录下这个最大值,再”添加“两个”伪”灯笼点,$0$ 与 $L$, 计算我们添加的”伪”灯笼点与已排序的首和尾灯笼的距离,与之前记录的最大值的一半进行比较,取三者的最大值进行输出
我的码码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int place[N];
int main()
{
int n, l;
cin >> n >> l;
int pmax = 0, pmin = l;
for(int i = 0; i < n; i++)
{
cin >> place[i];
pmax = max(pmax, place[i]);
pmin = min(pmin, place[i]);
}
sort(place, place + n);
int dismax = 0;
for(int i = 1; i < n; i++)
dismax = max(dismax, place[i] - place[i - 1]);
if(((dismax / 2) < pmin - 0) || ((dismax / 2) < l - pmax))
{
if(pmin - 0 > l - pmax)
printf("%.10lf", (pmin - 0) * 1.0);
else
printf("%.10lf", (l - pmax) * 1.0);
}
else
printf("%.10lf", dismax / 2.0);
}