3916: 攻与防(fight.cpp)
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：153
解决：28
题目描述
fight.in/out
有 n个战士站成一排，分别编号为 1,2,3. . .n，战士的战斗力等于他的编号 ，有一些战
士只会进攻，有一些战士只会防守。现在我们要将他们从某个点开始分成两个阵营，假设
这个点为 pos(0 ≤ pos ≤ n)，则编号小于等于pos的战士为第一个阵营，编号大于pos的战士
为第二个阵营。我们令第一个阵营为进攻方，第二个阵营为防守方，假设第一个阵营中能
够进攻的战士战斗力总和为 w，第二个阵营中能够防守的战士战斗力总和为 v，我们希望
∣ w − v ∣ 的值最小，其中 || 为绝对值符号。求 ∣ w-v ∣ 的最小值。
输入
第一行输入一个正整数 n，表示战士的数量（即后续给出的字符串的长度）。
第二行给出一个字符串s，仅由字符 0 或 1 组成，字符串中的每一位分别代表
每一位战士的属性，0 代表这个战士只会进攻，1 代表这个战士只会防守。
输出
一行一个整数表示答案。
样例输入 复制
4
0011样例输出 复制
1提示
【样例 1 说明】
假设我们在第二个位置切割，这样左边的字符串为 0，右边的字符串为 1，代表左
边有 2 个会进攻的战士，战斗力之和为 1 + 2 = 3，右边有 2 个会防守的战士，战斗
力之和为 3 + 4 = 7，即 |w-v| = |3 − 7| = 4。但如果我们在第三个位置切割，左边
的字符串为 001，右边的字符串为 1，此时左边会攻击的战士战斗力之和还是 3，右边
会防守的战士战斗力为 4，此时差值为 1，差值最小。
【样例 2 说明】
第二个样例可以在第五个位置分割，即左边的字符串为 10001，右边的字符串为01，代表左
边有 3 个会进攻的战士，2 个会防守的战士，所有会攻击战士的战斗力之和即 w= 2 + 3 + 4 =
9；右边有 1 个会防守的战士，1 个会进攻的战士，所有会防守的战士的战斗力之和为 v= 7。所
以 |9 − 7| = 2。
【数据范围】
对于 20% 的数据，n ≤ 10
对于 40% 的数据，n ≤ 1000
对于 100% 的数据，n ≤ 100000