分数: 425 点
问题陈述
给你一个字符串 S 长度 N 组成 0 和 1。可以保证 S 包含至少一个 1.
您可以执行以下操作任意次数(可能为零):
- 选择一个整数 i (1 \leq i \leq N-1)并交换 i-th 和 (i+1)- 第一个字符 S.
找到所需的最少操作数,以便所有 1是连续的。
这里,全部 1当且仅当存在整数时才被认为是连续的 l 和 r (1 \leq l \leq r \leq N)这样 i- 第一个字符 S is 1 当且仅当 l \leq i \leq r,和 0 否则。
约束
- 2 \leq N \leq 5 \times 10^5
- N 是一个整数。
- S 是长度 N 字符串
0和1. - S 包含至少一个
1.
输入
输入由标准输入按以下格式给出:
N S
输出
打印答案。
示例输入 1
7 0101001
示例输出 1
3
例如,以下三个操作使所有 1连续:
- 选择 i=2 并交换第二个和第三个字符。然后, S=
0011001. - 选择 i=6 并交换第 6 个和第 7 个字符。然后, S=
0011010. - 选择 i=5 并交换第 5 个和第 6 个字符。然后, S=
0011100.
不可能通过两次或更少的交换来做到这一点,所以答案是 3.
示例输入 2
3 100
示例输出 2
0
全部 1已经是连续的,因此不需要交换。
示例输入 3
10 0101001001
示例输出 3
7