算法-每天一道题(17)-路灯

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

输出描述:

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

输入例子:

7 15

15 5 3 7 9 14 0

输出例子:

2.50

C++

#include <iostream>
#include <vector>
#include <algorithm> // 使用sort和max函数

using namespace std;

int main(int argc, char const *argv[])
{
    int n, l;
    int temp;
    int max_num = 0;
    int boundary;
    while (cin>>n>>l)
    {
        vector<int> v(n);
        for (int i=0; i<n; i++)
            cin>>v[i];
        sort(v.begin(), v.end());
        for (int i=0; i<n; i++)
            max_num = max(v[i]-v[i-1], max_num);
        // 乘2是因为之后会除以2,并且间隔此时也没有除2的
        boundary = max(2*v[0], 2*(l-v[n-1]));
        max_num = max(max_num, boundary);
        printf("%.2f\n", float(max_num)/2.0);
        v.clear();
        max_num = 0;
    }
    return 0;
}

/*
解题思路:

贪心求解最大间隔/2
和边界比较
*/

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部