题解 | #路灯# 动态规划 求数组元素最大间距

需注意 最后要与保底的边界条件进行比较，才能得出正确值

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long l;
    while (cin >> n >> l) {
        vector<double> positions(n);
        int pos;
        for (int i = 0; i < n; i++) {
            cin >> pos;
            positions[i] = pos;
        }
        sort(positions.begin(), positions.end());
        // 遍历数组求两元素间的最大间距
        double maxDiff = 0 ;
        for (int i = 1; i < n; i++) {
            maxDiff = max(maxDiff, positions[i] - positions[i - 1]) ;
        }
        // 最大间距除以2才是一个灯的照明范围
        maxDiff /= 2.0;
        // 两个端点路灯的照明范围作为保底最小值
        double diff = max(positions[0], l - positions[n - 1]);
        // 跟保底值比较
        maxDiff = max(maxDiff, diff);
        cout << fixed << setprecision(2) << maxDiff << endl;
    }
    return 0;
}

时间复杂度：O(nlogn)，其中n为路灯的数量。主要是由于对路灯位置进行排序所导致的时间复杂度

空间复杂度：O(n)，主要是由于创建了一个大小为n的双精度浮点数向量positions来存储路灯的位置