首页 > 试题广场 >

路灯

[编程题]路灯
  • 热度指数：35632 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
一条长l的笔直的街道上有n个路灯，若这条街的起点为0，终点为l，第i个路灯坐标为ai ，每盏灯可以覆盖到的最远距离为d，为了照明需求，所有灯的灯光必须覆盖整条街，但是为了省电，要使这个d最小，请找到这个最小的d。

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


输出描述:
输出答案，保留两位小数。
示例1

输入

7 15
15 5 3 7 9 14 0

输出

2.50
算法知识视频讲解
添加回答
啊哈哈头像 啊哈哈 
/*
    渣渣解读： 
        本题实际上是求乱序数组中正序后的相邻元素最大差值。 
        如果暴力则时间复杂度O(n^2)；如果先排序再遍历，则时间复杂度O(nlogn)。
        所以可以用桶排序的思想，将n个数放入n+1个桶中，最大的放入n号桶，最小的放入0号桶，其他的计算桶后放入相应桶中， 
    每次放入时更新相应桶中的最大值及最小值，并设置标记表明此桶中有元素放入。由于桶的数量多于元素数量，所以必 
    定有桶中没有元素！桶内的最大差值小于桶间距，所以最大差值出现在：后一个有元素桶中的最小值 － 前一个有元素 
    的桶中的最大值。得出结果后除以2，并考虑边界情况后即是结果～
        时间复杂度O(n)，空间换时间
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

const int max_int = numeric_limits<int>::min();
const int min_int = numeric_limits<int>::max();

int getIndex(long elem, long n, long m_max, long m_min){
    return (int)((elem - m_min) * n/(m_max - m_min));
}

float getMaxDistance(const vector<int>& vi, const int n, const int m){
    int m_max = vi[0];
    int m_min = vi[0];
    for(int i = 1; i < n; ++i){
        m_max = m_max > vi[i] ? m_max : vi[i];
        m_min = m_min < vi[i] ? m_min : vi[i];
    }
    
    if(m_max == m_min)
        return max(m_max - 0, m - m_max);
    
    vector<bool> hasElem(n + 1, false);
    vector<int> maxElem(n + 1, max_int);
    vector<int> minElem(n + 1, min_int);
    for(int i = 0; i < n; ++i){
        int index = getIndex(vi[i], n, m_max, m_min);
        hasElem[index] = true;
        maxElem[index] = max(maxElem[index], vi[i]);
        minElem[index] = min(minElem[index], vi[i]);
    }
    
    int res, preMax, i = 0;
    while(i <= n){
        if(hasElem[i++]){
            preMax = maxElem[i - 1];
            break;
        }
    }
    for( ; i <= n; ++i){
        if(hasElem[i]){
            res = max(res, minElem[i] - preMax);
            preMax = maxElem[i];
        }
    }
    return max((float)res/2, (float)max(m_min - 0, m - m_max));
}

int main(){
    int n, m, tmp;
    vector<int> vi;
    while(cin>>n>>m){
        for(int i = 0; i < n; ++i){
            cin>>tmp;
            vi.push_back(tmp);
        }
        printf("%.02f\n", getMaxDistance(vi, n, m));
        vi.clear();
    }
    return 0;
}

发表于 2016-03-23 16:57:06 回复(0)
C/C++
牛客新手yhc头像 牛客新手yhc 
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
        
    int n, l;

    while(cin>>n>>l){

        double * arr = new double[n+1];

        for(int i = 0; i < n; i++) cin>>arr[i];
        sort(arr, arr+n);  // 排序

        double result = max(arr[0], l-arr[n-1]);  // 处理两个边界值
        for(int i = 1; i < n; i++)  // 循环判断是否有更大的距离
            result = (arr[i] - arr[i-1])/2.0 > result ? (arr[i] - arr[i-1])/2.0 : result;

        printf("%.2lf\n", result);  // 打印保留两位小数
    }
    return 0;
}

发表于 2018-05-07 12:45:57 回复(1)
夜小楼Dream头像 夜小楼Dream 
#Python版

# -*- coding:utf-8 -*-
import sys

if __name__ == '__main__':
    while True:
        nl = sys.stdin.readline().strip()
        if not  nl:
            break
        n,l =  [int(i) for i in nl.split(' ')]
        nums = [int(i) for i in sys.stdin.readline().strip().split(' ')]
        nums.sort()
        maxs = float('-inf')
        for i in range(n-1):
            maxs = max(maxs,nums[i+1]-nums[i])
        maxs = maxs/2.0

        maxs = max(maxs,nums[0]-0)
        maxs = max(maxs,l-nums[-1])
        print '%.2f'%(maxs)


发表于 2017-03-13 12:00:24 回复(0)
C/C++
武汉孙一峰头像 武汉孙一峰 
//需要考虑边界问题，第一个灯到0的距离，和最后一个灯到末尾的距离，是不用除2 的

#include "iostream"
#include "algorithm"
#define MAX 1005

using namespace std;

int n, l, a[MAX];
double minx;

int main()
{
	while (cin >> n >> l)
	{
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
		}
		a[0] = 0;
		a[n + 1] = l;
		sort(a, a + n + 2);

		minx = a[1];
		for (int i = 0; i <= n; i++)
		{
			double temp = a[i + 1] - a[i];
			if (i != n)
				temp /= 2;
			if (temp > minx)
				minx = temp;
		}

		printf("%.2f\n", minx);
	}
}

编辑于 2016-08-26 18:59:24 回复(1)
kiss90头像 kiss90 
/*(c/c++)
先对路灯坐标进行排序，然后求相邻路灯之间的最大间隔。需注意边界情况：路灯要照到边界，
那么它的照明距离应该为其到边界距离的二倍。输出结果要保留到小数点后2位。*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

int main()
{
    int n;
    long l;
    vector<long> v;
    int tmp;
    while(cin >> n >>l){
        v.clear();
        while(n--){
            cin >> tmp;
            v.push_back(tmp);
        }
        sort(v.begin(),v.end());

        long maxm=0;
        for(int i=0;i<v.size()-1;++i){
            if(v[i+1]-v[i]>maxm)
                maxm = v[i+1]-v[i];
        }
        int bianjie = max(2*(l-v[v.size()-1]),2*v[0]);
        if(maxm< bianjie)
            maxm = bianjie;

        printf("%.2f\n",maxm/2.0);

    }
    return 0;
}

发表于 2016-03-20 14:49:00 回复(18)
anybody头像 anybody 
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
int main()
{
	int n, L, i;
	while (cin >> n >> L)
	{
		vector<int> pos(n);
		for (i = 0; i < n; ++i)
			cin >> pos[i];
		sort(pos.begin(), pos.end());
		double res = max(pos[0],  L - pos[n - 1]);//边界判断
		int s = 0;
		for (i = 1; i < n; ++i)
			s = max(pos[i] - pos[i - 1], s);
		res = max(res, s / 2.0);
		cout << fixed << setprecision(2) << res << endl;
	}
	return 0;
}

发表于 2016-07-31 15:02:25 回复(1)
kestars头像 kestars 
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            int l=sc.nextInt();
            double max=0;
            int[] array=new int[n];
            for(int i=0;i<n;i++){
                array[i]=sc.nextInt();
            }
            Arrays.sort(array);
            for(int i=1;i<n;i++){
                if(array[i]-array[i-1]>max){
                    max=array[i]-array[i-1];
                }
            }
            if(array[0]*2>max){
                max=array[0]*2;
            }
            if((l-array[n-1])*2>max){
                max=(l-array[n-1])*2;
            }
            System.out.printf("%.2f",max/2);
            System.out.println();
        }
    }
}

发表于 2018-10-12 20:11:31 回复(0)
老石基头像 老石基 
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {//注意while处理多个case
            int n = in.nextInt();
            int l = in.nextInt();
            int[] a = new int[n];
            int max = 0;
            for(int i = 0;i<n;i++){
                a[i] = in.nextInt();
            }
            sort(a);
            int star = 0;
            for(int i = 0;i<n;i++){
                int d = a[i]-star;
                star = a[i];
                max = d>max?d:max;
            }
            if(a[n-1]!=l){
                int r = l-a[n-1];//比较特殊终点不是一盏灯
                max = r*2>max?r*2:max;

            }
            String result = String.format("%.2f",max/2.00);
            System.out.println(result);
        }
    }
    
    public static void sort(int[] a){
         
        for(int i = 0;i<a.length-1;i++){
            boolean flag = true;
            for(int j = 0;j<a.length-1-i;j++){
                if(a[j]>a[j+1]){
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                    flag = false;
                }
            }
            if(flag)
                return;
        }
    }
}

发表于 2016-04-10 19:08:45 回复(6)
天才哈哈哈哈头像 天才哈哈哈哈
简单易懂
对排序好的数组两两作差求解最大的间距max_cha（间距/2）
判断边界edge，因为整条路的坐标存在0和l点，若这两点没有路灯，则需要第一个灯或者最后一个灯可以照亮路头和路尾 
while True:
    try:
        n,l = map(int,input().split())
        a = sorted(list(map(int,input().split())))
        tmp = []
        i = 0
        while i>=0 and i < len(a)-1:
            tmp.append(a[i+1]-a[i])
            i += 1
        edge_strat = min(a) - 0
        edge_end = l - max(a)
        res = max(tmp)/2
        if res == max(edge_strat,edge_end,res):
            print(str(res)+'0')
        else:
            print(str(max(edge_strat,edge_end))+'.00')
    except:
        break


发表于 2022-04-02 16:18:14 回复(0)
C/C++
Debug丶头像 Debug丶
求最大差值， 
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int main()
{
    int nN, nL;
    while (cin >> nN >> nL)
    {
        set<int> setData;
        int nInput;
        for (int i = 0; i < nN; ++i)
        {
            cin >> nInput;
            setData.insert(nInput);
        }
        auto iter = setData.begin(), iterLast = setData.begin();
        int nMaxGap = 0;
        for (++iter; iter != setData.end(); ++iter, ++iterLast)
            if (nMaxGap < abs(*iter - *iterLast))
                nMaxGap = abs(*iter - *iterLast);
        double dRes = nMaxGap / 2.0;
        if (dRes < nL - *iterLast || dRes < *setData.begin())
        {
            nMaxGap = max(nL - *iterLast, *setData.begin());
            printf("%.2f\n", (double)nMaxGap);
            continue;
        }
        printf("%.2f\n", nMaxGap / 2.0);
    }
}

注意首位边界就行了
发表于 2019-08-27 17:16:21 回复(0)
菜鸡鑫头像 菜鸡鑫 
package recruit2016;

import java.util.Arrays;
import java.util.Scanner;
//画个图，想明白就很简单，找到两个坐标之间最大值，除以2即是d
//一个小坑，起点到第一个灯的值start和最后一个灯到终点的值end只能等于d
public class Practice42
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        while(in.hasNext())
        {
            int n = in.nextInt();
            int l = in.nextInt();
            int[] num = new int[n];
            for(int i=0; i<n; i++)
            {
                num[i] = in.nextInt();
            }
            Arrays.sort(num);//排个序，方便找最大差值
            int start = num[0] - 0;
            int end = l - num[n-1];
            int maxOfStartAndEnd = start>end ? start:end;
            double max = Double.MIN_VALUE;//找到路灯之间最大差值max
            for(int i=0; i<n-1; i++)
            {
                int temp = num[i+1] - num[i];
                if(max < temp)
                {
                    max = temp;
                }
            }
            //max/2跟起点到第一个灯的值start和最后一个灯到终点的值end比一下，最大的就是d
            double res = max/2>maxOfStartAndEnd ? max/2:maxOfStartAndEnd;
            System.out.println(String.format("%.2f", res));
        }
    }
}

发表于 2018-06-14 12:03:53 回复(1)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>

using namespace std;

int main()
{     int n,l,a[1010];     double Min;     while(cin>>n>>l)      {         for(int i=1;i<=n;i++)             cin>>a[i];         a[0] = 0;         a[n+1] = l;         sort(a, a+n+2);                  Min = a[1];         for(int i=0;i<=n;i++)         {             double d = a[i+1] - a[i];             if(i != n)                 d /= 2;             if(d > Min)                 Min = d;         }         printf("%.2f\n", Min);     }     return 0;
}

发表于 2017-12-09 04:30:00 回复(0)
CrazyCodingGirl头像 CrazyCodingGirl
这题不难，注意输出格式保留两位小数，， 
#include<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
using namespace std;
int main()
{
	int n, l;
	while (cin >> n >> l)
	{
		vector<int> loc(n, 0);
		for (auto &i : loc)
			cin >> i;
		sort(loc.begin(), loc.end());
		double temp = loc[0];
		for (int i = 1; i < n; i++)
		{
			if (loc[i] - loc[i - 1]>temp * 2)
				temp = (loc[i] - loc[i - 1]) / 2.0;
		}
		if (l - loc[n - 1] > temp)
			temp = l - loc[n - 1];
		cout <<fixed<<setprecision(2)<< temp << endl;
	}
	return 0;
}

发表于 2017-08-06 23:15:53 回复(0)
cycleof头像 cycleof 
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
int main(){
    int n,l;
    while( cin >> n >> l ){
        int i,j,a[1001];
        double maxx;
        for(i=0;i<n;i++)
            cin >> a[i];
        sort(a,a+n);//sort(首地址，要排序元素个数)
        maxx = max(a[0],l-a[n-1]);
        for(i=1;i<n;i++)
            maxx = max((a[i]-a[i-1])/2.0,maxx);//max(a,b) a,b应该类型相同！！
        cout << setiosflags(ios::fixed) << setprecision(2) << maxx <<endl;
    }
    return 0;
}
//把坐标点放入数组a中，再排序a，再将之间的距离差值/2,
//不断和max比较。注意首尾不用除2，要特殊处理。

编辑于 2017-06-22 14:34:32 回复(0)
Java
hello__bin头像 hello__bin 
import java.util.Scanner;
import java.math.BigDecimal;

public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        
        while(input.hasNext()){
        int n = input.nextInt();
        long l = input.nextLong();
        long[] lump = new long[n]; 
        
        for(int i = 0;i < n;i++){
            lump[i] = input.nextLong();
        }
        
        for(int i = 0;i < n -1;i++){
            for(int j = 0;j < n-i-1;j++){
                if(lump[j] > lump[j+1]){
                    long temp = lump[j];
                	lump[j] = lump[j+1];
                	lump[j+1] = temp;
                }
                  
            }
        }     
        
        
        long max = lump[1] - lump[0];
        for(int i = 2;i < n;i++){
            long current = lump[i] - lump[i - 1];
            if(max < current)
                max = current;
        }
        
        max = ((lump[0]-0)*2 > max)?(lump[0]-0)*2 : max;
        max = ((l - lump[n-1])*2 > max)?(l - lump[n-1])*2 : max;
        
        
        double result = (double) max / 2;
        BigDecimal bigDecimal = new BigDecimal(result);
        System.out.println(bigDecimal.setScale(2));
        }
    }
}
此题是动态规划题，要求的每盏灯的最远覆盖距离d的最小值（又最小又最大的，好像有点绕口，但是，从环保节能的角度来看，最小值才能最省电。）
我的解题思路是：因为最小值d一定要确保 全覆盖，所以要先对所有坐标进行排序，完了比较相邻坐标之间的距离，找出最大值，确保了最大值能满足要求就能保证全覆盖了。最后要比较边界值。
找出最大值后，求半，因为相邻之间两个路灯一个照明一半的路就行了。
发表于 2017-03-27 00:01:18 回复(0)
乐天知命头像 乐天知命 
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int n = in.nextInt();
			int len = in.nextInt();
			if (n <= 0 && n > Math.pow(10, 3) || len <= 0 && len > Math.pow(10, 9)) {
				return;
			}
			int[] nums = new int[n];
			for (int i = 0; i < n; i++) {
				nums[i] = in.nextInt();
			}
			for (int i = 0; i < n; i++) {
				if (nums[i] > len || nums[i] < 0) {
					return;
				}
			}
			String ans = getD(n, len, nums);
			System.out.println(ans);
		}
	}
	private static String getD(int n, int len, int[] nums) {
		// TODO Auto-generated method stub
		Arrays.sort(nums);
		double interval = 0;
		for (int i = 1; i < nums.length; i++) {
			interval = Math.max((nums[i] - nums[i - 1]), interval);
		}
		double ans = interval / 2;
		ans = Math.max(nums[0], Math.max(ans, (double) len - nums[n - 1]));
		return new DecimalFormat("0.00").format(ans);
	}
}

发表于 2017-03-25 12:58:26 回复(0)
已注销头像 已注销 
int main () {
    int n, l;
    while (cin >> n >> l) {
        vector<int> vec;
        for (int i = 0; i < n; ++i) {
            int loc = 0;
            cin >> loc;
            vec.push_back(loc);
        }
        sort(vec.begin(), vec.end());
        double dis = 0;
        for (int i = 0; i < n-1; ++i) {
                dis = max(dis, (vec[i+1] - vec[i])/2.0);
        }
        if (vec[0] != 0) dis = max(dis, (double)vec[0]);
        if (vec[n-1] != l) dis = max(dis, (double)(l - vec[n-1]));
        printf("%.2f\n", dis);
    }
    return 0;
}

发表于 2017-03-15 16:32:50 回复(0)
击水3千头像 击水3千 
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
int main(){
	long n,k;
    while(cin>>n>>k){
        vector<long>po;
        double max=0;
        long pre_po=0,cur_po;
        for(int i=0;i<n;++i){
            cin>>cur_po;
           po.push_back(cur_po);
        }
    	sort(po.begin(),po.end());
    	for(auto i: po){
         
            max=(max<(i-pre_po))?(i-pre_po):max;
            pre_po=i;
    	}
        max/=2;
        max=max>(k-*(--po.end()))?max:(k-*(--po.end()));
       cout<<fixed<<setprecision(2)<<max<<endl;
    }
}

编辑于 2017-03-03 16:14:17 回复(0)
谁是谁的眼头像 谁是谁的眼 
#include <stdio.h>

float maxLen(float num1,float num2,float num3)
{
	float max = num1;
	
	if(max<num2)
	{
		max = num2;
	}
	
	if(max<num3)
	{
		max = num3;
	}
	
	return max;
}

int main()
{
    int i;
	int j;
	int temp;
    int roadLength;
    int lightNum;
    
    while(scanf("%d%d",&lightNum,&roadLength) != EOF)
    {
		int location[lightNum];
		
     	for(i = 0; i < lightNum; i++)
        {
            scanf("%d",&location[i]);
        }
		
		for(i = 0; i < lightNum-1; i++)
		{
			for(j = i+1; j < lightNum; j++)
			{
				if(location[j]<location[i])
				{
					temp = location[i];
					location[i] = location[j];
					location[j] = temp;
				}
			}
		}
		
		int max = 0;
		
		for(i = 0; i < lightNum-1; i++)
		{
			if((location[i+1]-location[i])>max)
			{
				max = location[i+1]-location[i];
			}
		}
		
		printf("%.2f\n",maxLen((float)max/2,(float)location[0],(float)(roadLength-location[lightNum-1])));
    }
    
    return 0;
}

发表于 2016-08-30 09:30:49 回复(0)
VinerL头像 VinerL 
//没啥可说的，注意边界除不除2就好
#include <iostream>
#include <iomanip>
#include <set>
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
int n;
long l;
long a[1010];
int main(){
 	while(cin>>n>>l){
        set<long> st; 
        REP(i,n) {long t;cin>>t;st.insert(t);}
        double maximum=-1; int i=0;
        for(set<long>::iterator it=st.begin();it!=st.end();it++){a[i]=*it;i++;} 
        FOR(i,1,st.size()) maximum=a[i]-a[i-1]>maximum?a[i]-a[i-1]:maximum;
        maximum/=2; maximum=a[0]-0>maximum?a[0]-0:maximum;
        maximum=l-a[st.size()-1]>maximum?l-a[st.size()-1]:maximum;
        cout<<fixed<<setprecision(2)<<maximum<<endl;     
    }   
}

发表于 2016-07-29 14:25:13 回复(0)
提交观点

问题信息

动态规划
来自：网易2016校招研发工...
难度：
148条回答 24798浏览

热门推荐

通过挑战的用户

查看代码

相关试题

路灯

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号