110AC - ABC067C: Splitting Pile - back-of-the-envelope

ABC067-C (300 points)

問題

数列 $\{ a_1, a_2, \ldots , a_N \}$ に対して, $x = \sum_{i = 1}^{k} a_i$ , $y = \sum_{i = k + 1}^{N} a_i$ とするとき, $k \in \{1, \ldots , N - 1 \}$ に関する $|x - y|$ の最小値を求める.

$2 \leq N \leq 200,000$
$-10^9 \leq a_i \leq 10^9$

方針

$\left( x - y \right) _{k + 1} = \left(x - y \right) _{k} + 2 a_{k + 1}$
$k = 1, \ldots , N - 1$ に対して $\left( x - y \right) _{k}$ を求め, 絶対値を取って暫定解を更新していく.
一重forなので間に合う.

# input
N = int(input())
A = list(map(int, input().split()))

sum_A = sum(A)
temp = 2 * A[0] - sum_A
ans = abs(temp)

for i in range(1, N - 1):
    temp = temp + 2 * A[i]
    if abs(temp) < ans:
        ans = abs(temp)

print(ans)