← 返回题目列表

AtCoder · abc393_d

G. 交换收集

中文机器翻译题面 查看原题

分数: 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