华为机试-路灯覆盖问题
问题描述：
一条笔直的公路上安装了N个路灯，从位置0开始安装，路灯之间的距离是100m。每个路灯都有自己的照明半径，请计算第一个路灯和最后一个路灯之间，未照明区间的长度和。
输入描述：
第一行为一个数N，表示灯的个数，[1, 100000]
第二行为N个空格分隔的数，表示路灯的照明半径，[1, 100*100000]
输出描述：
第一个路灯和最后一个路灯之间，未照明区间的长度和
举例：
输入:
8
10 10 10 10 10 10 10 10
输出：
560
输入：
8
10 10 10 250 10 10 10 10
输出：
160
解析：
把首尾路灯之间的公路具体化为(N-1)*100段的列表S，初始全为0，表示未被照明。然后遍历每个路灯，将路灯能照到的范围内的0置位1，最后统计S中0的数量。
代码实现（Python3）
N = 8
r = [10, 10, 10, 10, 10, 10, 10, 10]
# N = int(input())
# r = list(map(int, input().split()))
S = [0 for _ in range((N-1) * 100)] # 首尾路灯之间的距离列表空间S，初始全赋值为0，表示每段都没有被照明
for i in range(N):
if i * 100 - r[i] < 0: # 灯光覆盖了左端，S中置换的位置也只能从第0位开始
left = 0
else:
left = i * 100 - r[i]
if i * 100 + r[i] > (N-1) * 100: # 灯光覆盖了右端，S中置换的位置也只能到第最后一位
right = (N - 1) * 100
else:
right = i * 100 + r[i]
S[left:right] = [1] * (right - left) # 灯光覆盖区域全标记为1
print(S.count(0)) # 统计没有被灯光覆盖区域
代码优化（Python3）
N = int(input())
r = list(map(int, input().split())) # 各路灯的半径
d = 100 # 路灯之间的距离均为100
S = [0 for _ in range((N-1) * d)] # 首尾路灯之间的距离空间，初始全赋值为0：表示没有被照明
for i in range(N):
left = max(0, i * d - r[i])
right = min((N-1) * d, i * d + r[i])
S[left:right] = [1] * (right - left) # 灯光覆盖区域全标记为1
print(S.count(0)) # 统计没有被灯光覆盖区域
#华为机试题#
查看17道真题和解析