基本算法思维——路灯问题

2021-02-07 02:15

阅读：446

标签：间隔一个 sys 最小 out ati 需要存在 ext

问题：

V先生有一天工作到很晚，回家的时候要穿过一条长l的笔直的街道，这条街道上有n个路灯。假设这条街起点为0，终点为l，第i个路灯坐标为ai。路灯发光能力以正数d来衡量，其中d表示路灯能够照亮的街道的点与路灯的最远距离，所有路灯发光能力相同。为了让V先生看清回家的路，路灯必须照亮整条街道，又为了节省电力希望找到最小的d是多少？

解决思路：实质是寻找最大间隔值

（1）边界：如果街道开始或结尾处没有安置路灯，间隔值为第一个路灯的值或最后一个路灯距离街尾的值。

（2）中间路灯：找到间隔最远的路灯，最后结果需要减半，因为此距离是两个路灯共同辐射的距离。

（3）综合前两种情况，取大。

code：

 1 import java.util.Arrays;
 2 import java.util.Scanner;
 3 public class Main {
 4     public static void main(String args[]) {
 5         Scanner s = new Scanner(System.in);
 6         int lamp_count = s.nextInt();
 7         int street_len = s.nextInt();
 8         int ar[] = new int[lamp_count];
 9         for(int i=0;i) {
10             ar[i] = s.nextInt();
11         }
12         //对路灯位置进行升序排序
13         Arrays.parallelSort(ar);
14         
15         double dif = 0;
16         //检查街道开始位置是否存在路灯
17         if(ar[0]!=0) {
18             dif=ar[0];
19         }
20         //检查街道末尾位置是否存在路灯
21         if(ar[lamp_count-1]!=street_len) {
22             dif = (street_len - ar[lamp_count-1])-dif>0?street_len - ar[lamp_count-1]:dif;
23         }
24         //检查中间路灯之间的间隔，
25         for(int i=1;i) {
26             double res = ar[i]-ar[i-1];
27             if((res/2)>dif) {
28                 dif =res/2;
29             }
30         }
31         s.close();
32         System.out.printf("%.2f",dif);
33     }
34 
35 }

基本算法思维——路灯问题

标签：间隔一个 sys 最小 out ati 需要存在 ext

原文地址：https://www.cnblogs.com/dream-flying/p/12780468.html

上一篇：python+selenium定位日期方法

下一篇：快速排序

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：基本算法思维——路灯问题
文章链接：http://soscw.com/index.php/essay/51973.html

亲，登录后才可以留言！

基本算法思维——路灯问题

评论

热门文章

推荐文章

最新文章

置顶文章