路灯 -- 2016网易笔试题

 

题目：

 一条长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

 

思路:这题只要把起点和终点都加入第二行进行排序,然后求出最大相邻的差值D,所求d=D/2;注意保留2位小数输出,将求出double保留2位小数的一种方法为

         String remain_d = String.format("%.2f", original_d);

下面是java代码实现:

package ustb.wangyi;
import java.util.Arrays;

public class StreetLamp {
    
    public static String getMinLightDist(int lampNum, int streetLen, int[] lampCoord) {
    
        if (lampNum <= 0 || lampNum > 1000) {
            throw new RuntimeException("街道灯的个数不符合要求");
        }
        
        if (streetLen <= 0 || streetLen > 1000000000) {
            throw new RuntimeException("街道的长度不符合要求");
        }
    
        if (lampNum != lampCoord.length) {
            throw new RuntimeException("数组中灯的个数与输入的灯的个数不一致");
        }
        
        for (int i = 0; i < lampCoord.length - 1; i++) {
            if (lampCoord[i] < 0 || lampCoord[i] > streetLen) {
                throw new RuntimeException("数组中第" + i + "个灯的坐标不符合要求");
            }
        }
        
        
        Arrays.sort(lampCoord);
        int maxAdjaDist = lampCoord[1] - lampCoord[0]; //初始化灯的最大相邻距离
        
        for (int i = 1; i < lampCoord.length - 1; i++) {
            int temp = lampCoord[i+1] - lampCoord[i];
            if (temp > maxAdjaDist)
                maxAdjaDist = temp;
        }
        
        //计算第一盏灯与街道起点的距离 和街道终点与最后一盏灯的距离
        int temp1 = lampCoord[0] - 0;
        int temp2 = streetLen - lampCoord[lampCoord.length - 1];
        maxAdjaDist = Math.max(maxAdjaDist, temp1);
        maxAdjaDist = Math.max(maxAdjaDist, temp2);
    
        double d = (double) maxAdjaDist / 2.0;
        String s =String.format("%.2f", d);
        return s;
    
    }
    
    public static void main(String[] args) {
        
        int[] lampCoord = {15, 5, 3, 7, 9, 14, 0};
        int streetLen = 15;
        int lampNum = 7;
        String d = getMinLightDist(lampNum, streetLen, lampCoord);
        System.out.println(d);
    }
    

}