一条长l的笔直的街道上有n个路灯，若这条街的起点为0，终点为l，第i个路灯坐标为ai ，每盏灯可以覆盖到的最远距离为d，为了照明需求，所有灯的灯光必须覆盖整条街，但是为了省电，要使这个d最小，请找到这个最小的d。
[编程题]路灯
注意这题有多组输入用例！题目没说。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
int l = scanner.nextInt();
int[] lights = new int[n];
for (int i = 0; i < n; i++) {
lights[i] = scanner.nextInt();
}
Arrays.sort(lights);
double ans = Math.max(lights[0], l - lights[n - 1]);
for (int i = 1; i < n; i++) {
double temp = (lights[i] - lights[i - 1]) / 2.0;
ans = Math.max(ans, temp);
}
System.out.printf("%.2f%n", ans);
}
}
}
发表于 2022-06-14 11:55:45
回复(0)
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();
int[] light=new int[n];
for(int i=0;i<n;i++){
light[i]=sc.nextInt();
}
Arrays.sort(light);
double max=0.0;
for(int i=1;i<n;i++){
max=Math.max(light[i]-light[i-1],max);
}
double res=0.0;
res=Math.max(max/2.0,Math.max(light[0],l-light[n-1]));
System.out.println(String.format("%.2f",res));
}
}
}
发表于 2021-08-31 10:32:59
回复(0)
本文算法步骤：
- 对获取到的路灯的位置数组locations进行排序，从小到大排序；
- 遍历locations,记录相邻元素的最大间距ans；
- 最小照明距离minD = ans / 2.0(不考虑边界条件);
- 考虑边界条件: minD = max(locations[0]-0, l-locations[-1], minD);
解释：数组内间距除以2是因为两个灯同时照亮这一段距离，边界不除以2是因为边界位置没有灯，所以第一个灯和最后一个灯要负责照亮整个距离。
import java.util.*;
import java.io.*;
import java.text.*;
public class Main{
public static void main(String[] args) throws IOException{
DecimalFormat df = new DecimalFormat("0.00");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
String[] temp;
while((line = br.readLine()) != null){
temp = line.split(" ");
int num = Integer.parseInt(temp[0]);
int len = Integer.parseInt(temp[1]);
String[] str2 = br.readLine().split(" ");
int[] locations = new int[num];
for(int i=0; i<num; i++){
locations[i] = Integer.parseInt(str2[i]);
}
int ans = 0;
// 排序 算最大间距 然后除2得ans
Arrays.sort(locations);
for(int i=1; i<num; i++){
ans = Math.max(ans, locations[i]-locations[i-1]);
}
double minD = ans/2.0;
minD = Math.max(minD, locations[0]);
minD = Math.max(minD, len-locations[num-1]);
System.out.println(df.format(minD));
}
}
}
发表于 2021-08-23 10:30:25
回复(0)
/*注意起始坐标和终点坐标*/
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();
long l = sc.nextLong();
PriorityQueue<Long> q = new PriorityQueue<>();
long max = 0;
for(int i = 0; i < n; i++){
q.add(sc.nextLong());
}
long cur = 0;
long first = q.peek();
while(!q.isEmpty()){
max = Math.max(max, q.peek() - cur);
cur = q.poll();
}
long end = l - cur;
if(Math.max(first, end) > max / 2) System.out.printf("%.2f", (float)Math.max(first, end));
else System.out.printf("%.2f", (float)max / 2);
System.out.println();
}
sc.close();
}
}
发表于 2020-08-15 14:11:46
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
// 读取输入，直到没有整型数据可读
while(cin.hasNextInt()) {
int n = cin.nextInt();
int l = cin.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++) {
arr[i] = cin.nextInt();
}
//练习快排
quickSort(arr,0,arr.length-1);
double max = 0.0;
//整数相除要转类型
for(int i=1;i<n;i++) {
max = Math.max(max,Double.valueOf((arr[i]-arr[i-1]))/2);
}
//边界距离不可忽视
max = Math.max(max, l-arr[n-1]);
max = Math.max(max, arr[0]);
String result = String.format("%.2f",max);
System.out.println(result);
}
}
public static void quickSort(int[] arr,int left,int right){
if(left>right) return;
int i=left,j=right;
int base = arr[left];
while(i!=j){
while(i<j && arr[j]>=base){
j--;
}
while(i<j && arr[i]<=base){
i++;
}
if(i<j){
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
}
arr[left] = arr[j];
arr[j] = base;
quickSort(arr,left,j-1);
quickSort(arr,j+1,right);
}
}
发表于 2020-08-07 18:02:48
回复(0)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
long ll = sc.nextInt();
long[] map = new long[n];
for (int i = 0; i < n; i++) {
map[i] = sc.nextLong();
}
Arrays.sort(map);
double max = map[0];
for (int i = 1; i < n; i++) {
double d = 1.0 * (map[i] - map[i - 1]) / 2;
max = max > d ? max : d;
}
max = max > (ll - map[n - 1]) ? max : (ll - map[n - 1]);
System.out.println(String.format("%1$.2f", max));
}
}
}
发表于 2018-09-30 14:35:51
回复(0)
import java.text.NumberFormat;
import java.util.Scanner;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
while (scanner.hasNext()) {
int n = scanner.nextInt();
int l = scanner.nextInt();
TreeSet<Integer> set = new TreeSet<>();
for (int i = 0; i < n; i++) {
set.add(scanner.nextInt());
}
int last = 0;
double d = 0;
for (Integer ld : set) {
double c = (ld - last) / 2.0;
if (c > d)
d = c;
last = ld;
}int c = l - last;
if (c > d)
d = c;
NumberFormat format = NumberFormat.getInstance();
format.setMaximumFractionDigits(2);
format.setMinimumFractionDigits(2);format.setGroupingUsed(false);
System.out.println(format.format(d));
}
}
}
}
发表于 2017-08-12 10:38:12
回复(0)
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();
int[] a=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
Arrays.sort(a);
//起始路灯照亮的距离
double dis=a[0];
//路灯之间的距离
double tem;
for(int i=1;i<n-1;i++){
tem=(a[i]-a[i-1])/2.0;
if(tem>dis)
dis=tem;
}
//最尾路灯的距离
tem=l-a[n-1];
if(tem>dis)
dis=tem;
System.out.printf("%.2f",dis);
}
}
}
编辑于 2017-04-23 20:02:58
回复(0)
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.*;
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();
int[] arr = new int[n];
for (int i = 0; i < arr.length; i ++ ) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr);
double max = 0;
for (int i = 1; i < arr.length; i ++ ) {
max = max > arr[i] - arr[i - 1] ? max : arr[i] - arr[i - 1];
}
max = max / 2;
max = max > l - arr[n - 1] ? max : l - arr[n - 1]; // 右边界条件
max = max > arr[0] ? max : arr[0]; // 左边界条件
System.out.println(new DecimalFormat("0.00").format(max));
}
sc.close();
}
}
发表于 2016-09-20 02:24:04
回复(0)
import java.util.Scanner;
import java.text.DecimalFormat;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int l = in.nextInt();
long[] num = new long[n];
for(int i = 0;i<n;i++){
num[i] = in.nextInt();
}
Arrays.sort(num);
long max = 0;
for(int i = 1;i<n;i++){
if(num[i]-num[i-1]>max)
max = num[i]-num[i-1];
}
long border = 2 * Math.max(l-num[n-1], num[0]);
if (border > max)
max = border;
System.out.println(new DecimalFormat("0.00").format((float)max/2));
}
}
}
1、典型贪心，排序，考虑边界情况
2、输入int溢出，所以要用long。
编辑于 2016-08-26 10:30:26
回复(0)
Scanner in = new Scanner(System.in);
int n;int l;
int[] t;
n = in.nextInt();l=in.nextInt();
t = new int[n];
for(int i=0;i<n;i++){
t[i] = in.nextInt();
}
double d=0.00;
for(int i=0;i<t.length-1;i++)
for(int j=0;j<t.length-1-i;j++)
{
if(t[j]>t[j+1])
{
int temp = t[j];
t[j]=t[j+1];
t[j+1]=temp;
}
}
for(int i =0 ;i<t.length-1;i++)
{
if(t[i+1]-t[i]>d)
d=t[i+1]-t[i];
}
d=d/2;
if(d<t[0]-1)
d=t[0]-1;
if(d<l-t[n-1])
d=l-t[n-1];
DecimalFormat df=new DecimalFormat("#.00");
System.out.println(df.format(d));
1.用数组记录路灯坐标，并对数组排序（从小到大）
2.记录排序后数组中相邻数据差值最大的值为d。
3.d/2作为输出记录，并比较开头结尾，用排序后最小位置路灯与0的差值，最大最值路灯与l的差值与d/2比较，最大的值即为最后输出
发表于 2016-08-06 12:55:29
回复(0)
import java.util.Scanner; import java.text.DecimalFormat; public class StreetLamp { public static void sort(int []a,int n){ for(int i=0;i<n-1;i++) for(int j=0;j<n-i-1;j++){ if(a[j]>a[j+1]){ int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } public static void main(String []args){ Scanner sc = new Scanner(System.in); DecimalFormat df = new DecimalFormat("######0.00"); while(sc.hasNext()){ int n = sc.nextInt(); //n个路灯 long l = sc.nextInt(); //距离为l int []a = new int[n]; for(int i=0;i<n;i++) a[i] = sc.nextInt(); sort(a,n); double max = 2*a[0]; for(int i=0;i<n-1;i++){ int temp = a[i+1]-a[i]; if(max<temp) max = temp; } if(a[n-1]!=l){ if(max/2<l-a[n-1]){ max = l - a[n - 1]; System.out.println(df.format(max)); } else System.out.println(df.format(max/2)); } else System.out.println(df.format(max/2)); } } }
编辑于 2016-08-02 14:41:15
回复(0)
import java.text.DecimalFormat;
import java.util.Scanner;
/**
* 一条长l的笔直的街道上有n个路灯，若这条街的起点为0，终点为l，第i个路灯坐标为ai，
* 每盏灯可以覆盖到的最远距离为d，为了照明需求，所有灯的灯光必须覆盖整条街，
* 但是为了省电，要是这个d最小，请找到这个最小的d。
*
* 每组数据第一行两个整数n和l（n大于0小于等于1000，l小于等于1000000000大于0）。
* 第二行有n个整数(均大于等于0小于等于l)，为每盏灯的坐标，多个路灯可以在同一点。
* @author kexun
*
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
int i = in.nextInt();
int[] list = new int[n];
for (int j=0; j<n; j++) {
list[j] = in.nextInt();
}
sort(list);
long maxDist = 0;
for (int k=0; k<n-1; k++) {
int temp = list[k+1] - list[k];
if (temp > maxDist) {
maxDist = temp;
}
}
DecimalFormat df = new DecimalFormat("0.00");
long result;
long lastDist = (long) ((i-list[list.length-1])*1.0);
long firstDist = (long) (list[0]*1.0);
if (firstDist > lastDist) {
result = firstDist;
} else {
result = lastDist;
}
if ((long) (maxDist/2.0) > result) {
System.out.println(df.format(maxDist/2.0));
} else {
System.out.println(df.format(result));
}
}
}
public static void sort(int[] list) {
int length = list.length;
if (length <= 1) {
return;
}
for (int i=0; i<length; i++) {
for (int j=length-1; j>i; j--) {
if (list[j] < list[j-1]) {
int temp = list[j];
list[j] = list[j-1];
list[j-1] = temp;
}
}
}
}
}
发表于 2016-07-23 09:51:05
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-12-11 17:05:43 -
2022-09-15 03:07:09 -
2022-09-14 09:25:24
-
2022-09-09 23:32:12 -
2022-09-09 22:03:49
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
