問題一覧 > 通常問題

No.1437 01 Sort

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 4
作問者 : tyawanmusityawanmusi / テスター : cn_449cn_449
0 ProblemId : 5527 / 出題時の順位表
問題文最終更新日: 2021-03-16 15:14:08

問題文

茶碗蒸しくんは長さ $N\ (N \ge 2)$ の 0 , 1 からなる文字列 $S$ を持っています。

茶碗蒸しくんは以下の操作を $0$ 回以上繰り返します。

  • $S$ の末尾の文字を取り除き、取り除いた文字を先頭に追加するか、または先頭から $2$ 番目に挿入する。

茶碗蒸しくんが $S$ をソートするために必要な操作回数の最小値を求めてください。

ただし、 $S$ がソートされているとは、例えば 000011111 のように、 10 より前に存在しないことを意味します。

制約

  • $N$ は整数
  • $2 \le N \le 10^5$
  • $S$ は 0 , 1 からなる長さ $N$ の文字列

入力

$N$
$S$

$1$ 行目には整数 $N$ が、 $2$ 行目には文字列 $S$ が入力されます。

出力

必要な操作回数の最小値を整数で $1$ 行に出力してください。 最後に改行してください。

また、この問題の設定下において、どのような文字列も有限回の操作でソートできることが証明できます。

サンプル

サンプル1
入力
4
1010
出力
3

以下のように操作することでソートできます。

  • 末尾の文字を取り除き、 先頭に追加する。
  • 末尾の文字を取り除き、 先頭から $2$ 番目に挿入する。
  • 末尾の文字を取り除き、 先頭に追加する。

$S$ は 1010010101100011 のように変化します。

これより小さい操作回数でソートすることはできないため、 $3$ が答えとなります。

サンプル2
入力
6
001001
出力
7

001001100100100010010001011000001100000110000011 の手順でソートできます。

サンプル3
入力
8
01010101
出力
11

(ΦωΦ)フフフ…

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。