xiaozhao_001

转载请注明出处，谢谢！（原文链接：https://chensian.github.io/2016/12/24/xiaozhao_001/ ）

链接：https://www.nowcoder.com/practice/62cdf520b9d94616b6644ac03a0306ff?tpId=49&tqId=29309&tPage=3&rp=3&ru=/ta/2016test&qru=/ta/2016test/question-ranking

来源：牛客网

题目描述

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

输入描述:

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

输出描述:

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

输入例子:

7 15
15 5 3 7 9 14 0

输出例子:

2.50

解题思路

改题可转化为求乱序数组排序后的元素之间最大距离

改题最简单的做法就是

15 5 3 7 9 14 0

排序 0 3 5 7 9 14 15

最大距离为 9 -> 14 为 5

所以 d = 5 / 2 = 2.50

源代码

import java.util.Scanner;
import java.math.BigDecimal;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            long l = in.nextLong();    
            long[] array = new long[n];
            for(int i=0;i<n;i++){
                array[i] = in.nextLong();
            }
            // 冒泡排序
            for (int i=0;i<n;i++){
                for(int j=0;j<n-i-1;j++){
                    if(array[j]>array[j+1]){
                        long temp=array[j];
                        array[j]=array[j+1];
                        array[j+1]=temp;
                    }
                }
            }
            // 找出数组相邻元素的最大距离
            long maxLength = 0;
            for(int i=1;i<n;i++){
                if(array[i]-array[i-1] > maxLength){
                    maxLength = array[i]-array[i-1];
                }
            }
            // 边界处理
            maxLength = ((array[0]-0)*2 > maxLength)?(array[0]-0)*2:maxLength;
            maxLength = ((l-array[n-1])*2 > maxLength)?(l-array[n-1])*2:maxLength; 
            double reusult=(double)maxLength/2;
            BigDecimal bigDecimal=new BigDecimal(reusult);
            System.out.println(bigDecimal.setScale(2));
        }
    }
}