3724: 攻与防(第四轮02)
题目描述
有 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 输入】
4
0011
【样例 1 输出】
1
【样例 1 说明】
假设我们在第二个位置切割，这样左边的字符串为 0，右边的字符串为 1，代表 左边有 2 个会进攻的战士， 战斗力之和为 1 + 2 = 3，右边有 2 个会防守的战 士，战斗力之和为 3 + 4 = 7，即 |w − v | = |3 − 7| = 4。但如果我们在第三个位 置切割，左边的字符串为 001，右边的字符串为 1，此时左边会攻击的战士战斗 力之和还是 3，右边会防守的战士战斗力为 4，此时差值为 1，差值最小。
【样例 2 输入】
7
1000101
【样例 2 输出】
2
【样例 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