华为OD机试真题-路灯照明问题（Java/C++/Go/Python）

【华为OD机试真题】路灯照明问题（Java/C++/Go/Python）

题目描述

在一条笔直的公路上安装了N个路灯，从位置0开始安装，路灯之间间距固定为100米。

每个路灯都有自己的照明半径，请计算第一个路灯和最后一个路灯之间，无法照明的区间的长度和。

输入描述

第一行为一个数N，表示路灯个数，1<=N<=100000

第二行为N个空格分隔的数，表示路灯的照明半径，1<=照明半径<=100000*100

输出描述

第一个路灯和最后一个路灯之间，无法照明的区间的长度和

用例1

输入

2

50 50
1
2
3

输出

0
1

用例2

输入

4

50 10000 20 30
1
2
3

输出

0
1

说明

路灯1覆盖0-50，路灯2覆盖50-100，

路灯1和路灯2之间(0米-100米)无未覆盖的区间。

解题思路

1.先将路灯的照明范围转化为区间，存入二维数组

2.数组排序后，求并集，然后将区间之间的间隔相加

考点

区间交并集

代码

Java代码

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt(); // 读取路灯个数
    int[] rad = new int[n]; // 存储每个路灯的照明半径
    for (int i = 0; i < n; i++) {
        rad[i] = scanner.nextInt(); // 读取每个路灯的照明半径
    }
    // 计算无法照明的区间的长度和
    long totalLength = 0;
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            totalLength += (long)(rad[i] + rad[i - 1] - 100); // 当前路灯与前一个路灯之间的区间长度
        }
        if (i < n - 1) {
            totalLength += (long)(rad[i] + rad[i + 1] - 100); // 当前路灯与后一个路灯之间的区间长度
        }
    }
    // 输出结果
    System.out.println(totalLength);
    scanner.close();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这个Java代码首先读取路灯的个数和每个路灯的照明半径。接下来，它使用一个循环来计算无法照明的区间的长度和。
在每次迭代中，它计算当前路灯与前一个路灯之间以及当前路灯与后一个路灯之间的区间长度，
并将它们累加到totalLength变量中。最后，输出totalLength的值作为结果。
需要注意的是，由于题目中给出的路灯个数和照明半径的范围很大，因此需要使用长整型变量来存储totalLength，以避免整数溢出的问题。
1
2
3
4

C++代码

// 导入所有常用库的头文件  
#include   
  
// 使用C++标准命名空间，使得程序中可以直接使用如cout、vector等名称  
using namespace std;  
// 主函数开始，C++程序的入口点  
int main() {  
    // 定义一个整数变量n，从接下来的输入中读取其值  
    int n;  
    cin>>n;  
    // 定义一个整数向量vec，其大小为n，并使用线性公式i*100来填充它  
    vector<int> vec(n);  
    for(int i=0;i<n;i++) {  
        vec[i]=100*i;  
    }  
    // 定义一个二维向量arr，它将会存储区间信息  
    vector<vector<int>> arr;  
    // 循环n次，每次读取一个tmp值（实际为区间的宽度）  
    for(int i=0;i<n;i++) {  
        int tmp;  
        cin>>tmp;  
        // 计算区间的上下限，根据输入的tmp值和vec中的值来确定  
        int low=max(0,vec[i]-tmp);  
        int hi=min(vec[n-1],vec[i]+tmp);  
        // 将计算出的区间上下限作为元素添加到arr向量中  
        arr.push_back({low,hi});  
    }  
    // 定义一个二维向量res，用于存储排序后的区间信息  
    vector<vector<int>> res;  
    // 使用默认的排序规则对arr向量进行排序，从小到大  
    sort(arr.begin(),arr.end());  
    // 将排序后的arr向量的第一个元素添加到res向量中  
    res.push_back(arr[0]);  
    // 循环遍历arr向量中的每一个元素（除了第一个元素）  
    for(int i=1;i<arr.size();i++) {  
        // 分别获取当前元素的下限和上限  
        int from=arr[i][0];  
        int to=arr[i][1];  
        // 如果当前元素的下限小于或等于res中最后一个元素的第二个值（即上限）  
        // 那么更新res中最后一个元素的上限为当前元素的上限和res中最后一个元素的上限的较大值  
        if(from<=res[res.size()-1][1]){  
            res[res.size()-1][1]=max(to,res[res.size()-1][1]);  
        }else{  
            // 如果当前元素的下限大于res中最后一个元素的第二个值，那么在res中添加一个新的元素，下限为当前元素的下限，上限为当前元素的上线  
            res.push_back({from,to});  
        }  
    }  
    // 定义一个变量ans，初始值为0，用于存储最后的结果  
    int ans=0;  
    // 循环遍历res向量中的元素（从第二个元素开始，即索引为1的元素），将每个元素的上限减去前一个元素的下限并累加到ans变量上  
    for(int i=1;i<res.size();i++) {  
        ans+=res[i][0]-res[i-1][1];  
    }  
    // 输出最终结果ans，然后暂停程序执行，等待用户输入或按任意键继续执行  
    cout<<ans<<endl;  
    system("pause");  
    return 0;  // 主函数结束，返回0表示程序正常退出  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

Python代码

n=int(input())  #从标准输入读取一个整数，赋值给变量n  
vec=list(map(int,input().split()))  # 从标准输入读取一行字符串，并将其中的每个整数转换为int类型后存入列表vec  
hi=(n-1)*100  #计算hi的值，为(n-1)乘以100  
arr=[]  #初始化一个空列表arr 
for i in range(n):  #循环n次，每次循环对于列表vec中的当前元素和对应的索引i进行以下操作  
    a=max(0,100*i-vec[i]) #计算a的值，为100乘以当前索引i减去列表vec中当前索引i的元素值，再与0之间取最大值   
    b=min(hi,100*i+vec[i]) #计算b的值，为hi和100乘以当前索引i加上列表vec中当前索引i的元素值的较小值  
    arr.append([a,b])      #将a和b的值作为一个列表添加到arr列表中  
res=[]  #初始化一个空列表res  
arr.sort(key=lambda x:(x[0],x[1])) #使用lambda函数将arr列表中的元素按照第一个元素排序，如果第一个元素相同则按照第二个元素排序  
for i in arr:  #循环arr列表中的每个元素，即每次循环对res列表进行以下操作  
    if len(res)==0:   #如果res列表目前为空，将当前元素添加到res列表中并继续下一次循环  
        res.append(i)  
        continue  
    if i[0]>res[-1][1]:  #如果当前元素的第一个值大于res列表最后一个元素的第二个值，将当前元素添加到res列表中  
        res.append(i)  
    else:  
        res[-1][1]=max(res[-1][1],i[1])   #否则，将res列表最后一个元素的第二个值更新为当前元素第二个值和res列表最后一个元素的第二个值中的最大值  
ans=0  #初始化一个变量ans为0  
for i in range(1,len(res)):  #循环res列表中的每个元素，从第二个元素开始（索引为1），对ans进行以下操作  
    if res[i][0]>res[i-1][1]: #如果res列表中当前元素的第一个值大于前一个元素的第二个值，将当前元素的第一个值减去前一个元素的第二个值加到ans上  
        ans+=res[i][0]-res[i-1][1]
print(ans)	#打印ans的值  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Go代码

package main  
  
import (  
 "fmt"  
)  
  
func main() {  
 var N int  
 fmt.Scanln(&N) // 读取路灯个数  
  
 radii := make([]int, N) // 存储每个路灯的照明半径  
 for i := 0; i < N; i++ {  
 fmt.Scan(&radii[i]) // 读取每个路灯的照明半径  
 }  
  
 // 计算无法照明的区间的长度和  
 var totalLength int  
 for i := 0; i < N; i++ {  
 if i > 0 {  
 totalLength += (radii[i] + radii[i-1] - 100) // 当前路灯与前一个路灯之间的区间长度  
 }  
 if i < N-1 {  
 totalLength += (radii[i] + radii[i+1] - 100) // 当前路灯与后一个路灯之间的区间长度  
 }  
 }  
  
 fmt.Println(totalLength) // 输出结果  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

这段代码首先读取路灯的个数和每个路灯的照明半径。然后，使用一个循环来计算无法照明的区间的长度和。在每次迭代中，它计算当前路灯与前一个路灯之间以及当前路灯与后一个路灯之间的区间长度，并将它们累加到totalLength变量中。最后，输出totalLength的值作为结果。
注意，在读取输入时，使用fmt.Scanln()函数来读取整数值。而在输出结果时，使用fmt.Println()函数来打印结果。另外，为了方便计算，将照明半径存储在一个切片中，使用索引来访问每个路灯的照明半径。
1
2