路燈照明II

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

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

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

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

python實(shí)現(xiàn):

• 區(qū)間合并問(wèn)題，計(jì)算區(qū)間，區(qū)間排序

n = int(input().strip())
arr = list(map(int, input().strip().split()))
internal = 100# 計(jì)算每個(gè)路燈的覆蓋區(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])# 按照每個(gè)區(qū)間的起始值升序排序
cover_area.sort(key=lambda i:i[0])# 計(jì)算陰影區(qū)域
result = 0
for i in range(1, n, 1):if cover_area[i][0] <= cover_area[i-1][1]:# 無(wú)陰影continueresult += cover_area[i][0] - cover_area[i-1][1]print(result)