A5076 | $午枫的又一个01串$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

小枫有一个长度为 $n$ 的 $01$ 串 $s$ ，这个 $01$ 串从左往右的第 $i$ 个数为 $s_i$ ，小午可以对这个 $01$ 串做最多 $m$ 次操作： 选择一段区间 $[l,r]$ 满足 $1 \leq l r \leq n, s_l=0,s_r=1$ 。 对于这段区间的每一位 $s_i(l\leq i \leq r)$ ，将其变为 $s_i \oplus 1$ ，其中 $\oplus$ 表示按位异或。 定义一个 $01$ 串的度为相邻两位不同的个数。形式化的，对于 $1\leq i\leq n-1$ ，满足 $s_i\neq s_{i+1}$ 的个数为 $01$ 串的度。 小枫想知道小午通过操作最多 $m$ 次后，在所有能得到的字符串中最小的度为多少。

第一行输入两个整数 $n,m$ $(1\leq n,m\leq 10^6)$ ，分别表示 $01$ 串的长度以及最多操作次数。 第二行输入一个长度为 $n$ 的 $01$ 串 $s$ ，表示初始的 $01$ 串。

输出一个整数，表示在所有能得到的字符串中，最小的度。

输入 #1

8 1
10111001

输出 #1

C++ 编辑器

输入

输出