路燈照明II

• 在一條筆直的公路上安裝了N個路燈，從位置0開始安裝，間距固定為100米；
• 每個路燈都有自己的照明半徑，計算第一個路燈和最后一個路燈之間，無法照明的區(qū)間長度和；

輸入描述:
第一行輸入路燈個數(shù)N；
第二行輸入路燈照明半徑
輸出描述:
第一個路燈和最后一個路燈之間，無法照明的區(qū)間長度和；

示例1
輸入：
2
50 50
輸出：
0

示例2
輸入：
4
50 70 20 70
輸出：
20

python實現(xiàn):

• 區(qū)間合并問題，計算區(qū)間，區(qū)間排序

n = int(input().strip())
arr = list(map(int, input().strip().split()))
internal = 100# 計算每個路燈的覆蓋區(qū)間
cover_area = []
for i in range(n):if i == 0:start = 0end = arr[i]elif i != n - 1:start = i * internal - arr[i]end = i * internal + arr[i]else:start = i * internal - arr[i]end = i * internalcover_area.append([start, end])# 按照每個區(qū)間的起始值升序排序
cover_area.sort(key=lambda i:i[0])# 計算陰影區(qū)域
result = 0
for i in range(1, n, 1):if cover_area[i][0] <= cover_area[i-1][1]:# 無陰影continueresult += cover_area[i][0] - cover_area[i-1][1]print(result)