Subscribed unsubscribe Subscribe Subscribe

0w1

CFR 803 B. Distances to Zero ( Ad hoc )

Problem - B - Codeforces

題意:
給一個數列,其中至少有一個元素為 0。對每一個位置輸出離它最近的 0 的距離。

制約:
The first line contains integer n (1 ≤ n ≤ 2e5) — length of the array a. The second line contains integer elements of the array separated by single spaces ( - 1e9 ≤ ai ≤ 1e9).

解法:
從左邊往右掃一次,記錄最靠右的 0 的位置更新。再由右往左做一次。

時間 / 空間複雜度:
O( N )

N = int( input() )
A = list( map( int, input().split() ) )
ans = [ N for i in range( N ) ]
prev = -N
for i in range( N ):
  if A[ i ] == 0:
    prev = i
  ans[ i ] = i - prev
prev = N + N
for i in range( N - 1, -1, -1 ):
  if A[ i ] == 0:
    prev = i
  ans[ i ] = min( ans[ i ], prev - i )
print( *ans )