Balance

题目描述

我们有 $N$ 个权重，索引为 $1$ 到 $N$。索引为 $i$ 的砝码的质量是 $W_i$。 我们将这些砝码分成两组：对于某个整数 1 \leq T < N，一组是索引不大于 $T$ 的砝码，另一组是索引大于 $T$ 的砝码。令 $S_1$ 为前一组中砝码质量的总和，$S_2$ 为后一组中砝码质量的总和。 考虑所有可能的这种划分，求 $S_1$ 和 $S_2$ 绝对差的最小可能值。

输入格式

输入从标准输入按如下格式给出： $N$ $W_1$ $W_2$ $...$ $W_{N-1}$ $W_N$

输出格式

输出 $S_1$ 和 $S_2$ 绝对差的最小可能值。

3
1 2 3

0

4
1 3 1 1

2

8
27 23 76 2 3 5 62 52

2

提示

$2 \leq N \leq 100$ $1 \leq W_i \leq 100$ 输入中的所有数值均为整数。如果 $T = 2$，$S_1 = 1 + 2 = 3$ 且 $S_2 = 3$，绝对差为 $0$。
如果 $T = 2$，$S_1 = 1 + 3 = 4$ 且 $S_2 = 1 + 1 = 2$，绝对差为 $2$。我们无法得到更小的绝对差。

标签: AtCoder|abc129B

来源

AtCoder|abc129B