网易 路灯 动态规划

网易 路灯 动态规划

题目描述

一条长l的笔直的街道上有n个路灯,若这条街的起点为0,终点为l,第i个路灯坐标为ai ,每盏灯可以覆盖到的最远距离为d,为了照明需求,所有灯的灯光必须覆盖整条街,但是为了省电,要使这个d最小,请找到这个最小的d。

输入描述:

每组数据第一行两个整数n和l(n大于0小于等于1000,l小于等于1000000000大于0)。第二行有n个整数(均大于等于0小于等于l),为每盏灯的坐标,多个路灯可以在同一点。

输出描述:

输出答案,保留两位小数。

示例1

输入

7 1515 5 3 7 9 14 0

输出

2.50
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define ll long long int
const int maxn = 1e3+5;
#define INF 1<<30
#define max(x,y) ((x)>(y)?(x):(y))
int arr[maxn];
int main()
{
    ll n,dis;
    while(cin>>n>>dis)
    {
        for(int i=0;i<n;++i) cin>>arr[i];
        sort(arr,arr+n);
        double ans = -INF;
        for(int i=1;i<n;++i) 
        {
            ans=max(ans,(arr[i]-arr[i-1]));
        }
//        for(int i=0;i<n;++i)
//        {
//            cout<<arr[i];
//        }
//        cout<<endl;
//        cout<<ans<<endl;
        ans/=2;
        ans=max( max(ans,arr[0]),max(ans,(dis-arr[n-1])) );
        printf("%.2lf\n",ans);
    }
    return 0;
}
Last modification:January 11th, 2020 at 10:34 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment