ARC 072 C - Sequence ( Greedy )

C: Sequence - AtCoder Regular Contest 072 | AtCoder

題意：
給 N 個數字的數列 A。一次操作選一個數字 +1 或 -1。問最少要幾次操作，才能使得前綴和的正負交替。

制約：
2≦n≦1e5
|ai|≦1e9
ai は整数

解法：
枚舉開頭是正或負。由左到右確定數字，只有在必要的時候，貪心進行最少操作。

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

N = int( input() )
A = list( map( int, input().split() ) )
s = 0
f = 0
for i in range( N ):
  s += A[ i ]
  x = s
  if i & 1: # -> -1
    if x < 0: continue
    s -= x - ( -1 )
    f += x - ( -1 )
  else:
    if x > 0: continue
    s += 1 - x
    f += 1 - x
s = 0
g = 0
for i in range( N ):
  s += A[ i ]
  x = s
  if ~i & 1: # -> -1
    if x < 0: continue
    s -= x - ( -1 )
    g += x - ( -1 )
  else:
    if x > 0: continue
    s += 1 - x
    g += 1 - x
print( min( f, g ) )