D - Swap to Gather Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

0 および 1 からなる長さ N の文字列 S が与えられます。 ここで、S には 1 が 1 つ以上含まれることが保証されます。

あなたは、以下の操作を繰り返し（0 回でも良い）行うことができます。

  • 1\leq i\leq N-1 を満たす整数 i を選び、S の i 文字目と i+1 文字目を入れ替える。

すべての 1 がひとかたまりになった状態にするために必要な操作回数の最小値を求めてください。

なお、すべての 1 がひとかたまりになっているとは、ある整数 l,r\ (1\leq l\leq r\leq N) が存在し、 S の i 文字目は l\leq i\leq r ならば 1、そうでないならば 0 であることをいいます。

制約

  • 2\leq N\leq 5\times 10^5
  • N は整数
  • S は 0 および 1 からなる長さ N の文字列
  • S には 1 が 1 つ以上含まれる

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

答えを出力せよ。

入力例 1

7
0101001

出力例 1

3

例えば、以下のように操作を 3 回行うと、すべての 1 がひとかたまりになります。

  • i=2 を選び、S の 2 文字目と 3 文字目を入れ替える。S= 0011001 になる。
  • i=6 を選び、S の 6 文字目と 7 文字目を入れ替える。S= 0011010 になる。
  • i=5 を選び、S の 5 文字目と 6 文字目を入れ替える。S= 0011100 になる。

2 回以下の操作ですべての 1 をひとかたまりにすることはできないため、答えは 3 です。

入力例 2

3
100

出力例 2

0

既にすべての 1 がひとかたまりになっているため、操作は必要ありません。

入力例 3

10
0101001001

出力例 3

7

Score : 425 points

Problem Statement

You are given a string S of length N consisting of 0 and 1. It is guaranteed that S contains at least one 1.

You may perform the following operation any number of times (possibly zero):

  • Choose an integer i (1 \leq i \leq N-1) and swap the i-th and (i+1)-th characters of S.

Find the minimum number of operations needed so that all 1s are contiguous.

Here, all 1s are said to be contiguous if and only if there exist integers l and r (1 \leq l \leq r \leq N) such that the i-th character of S is 1 if and only if l \leq i \leq r, and 0 otherwise.

Constraints

  • 2 \leq N \leq 5 \times 10^5
  • N is an integer.
  • S is a length N string of 0 and 1.
  • S contains at least one 1.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

7
0101001

Sample Output 1

3

For example, the following three operations make all 1s contiguous:

  • Choose i=2 and swap the 2nd and 3rd characters. Then, S= 0011001.
  • Choose i=6 and swap the 6th and 7th characters. Then, S= 0011010.
  • Choose i=5 and swap the 5th and 6th characters. Then, S= 0011100.

It is impossible to do this in two or fewer swaps, so the answer is 3.

Sample Input 2

3
100

Sample Output 2

0

All 1s are already contiguous, so no swaps are needed.

Sample Input 3

10
0101001001

Sample Output 3

7