No.1437 01 Sort
タグ : / 解いたユーザー数 9
作問者 :
cn_449
Problem Statement
Chawanmushi-kun has a string $S$ of length $N\ (N \ge 2)$ consisting of 0 and 1.
Chawanmushi-kun repeats the following operation $0$ or more times.
- Remove the last character of $S$, and either add the removed character to the beginning or insert it at the $2$-nd position from the beginning.
Find the minimum number of operations Chawanmushi-kun needs to sort $S$.
Here, $S$ being sorted means that no 1 appears before a 0, as in 000011111, for example.
Constraints
- $N$ is an integer
- $2 \le N \le 10^5$
- $S$ is a string of length $N$ consisting of
0and1
Input
$N$ $S$
The $1$-st line contains an integer $N$, and the $2$-nd line contains a string $S$.
Output
Output the minimum number of operations required as an integer on $1$ line. Print a newline at the end.
Note that, under the settings of this problem, it can be proved that any string can be sorted in a finite number of operations.
Sample
Sample 1
Input
4 1010
Output
3
It can be sorted by operating as follows.
- Remove the last character and add it to the beginning.
- Remove the last character and insert it at the $2$-nd position from the beginning.
- Remove the last character and add it to the beginning.
$S$ changes as 1010 → 0101 → 0110 → 0011.
It cannot be sorted in fewer operations, so the answer is $3$.
Sample 2
Input
6 001001
Output
7
It can be sorted by the procedure 001001 → 100100 → 100010 → 010001 → 011000 → 001100 → 000110 → 000011.
Sample 3
Input
8 01010101
Output
11
(ΦωΦ)フフフ…
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。