← 返回题目列表

Codeforces · 774/L

L. 酒吧

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

Polycarp 的工作日正好持续 $$$n$$$ 分钟。他喜欢巧克力,并且可以在一分钟内吃掉一根巧克力。今天,Polycarp 在工作日开始时有 $$$k$$$ 酒吧。

工作日的某些分钟里,波利卡普有重要的事情要做,而在这些分钟里他无法吃巧克力棒。在其他几分钟内,他可以吃或不吃一块巧克力。可以保证的是,在工作日的第一分钟和最后几分钟,波利卡普没有什么重要的事情要做,他总是会在这几分钟里吃酒吧,让自己在工作日开始和结束时感到高兴。还可以保证 $$$k$$$ 严格大于 $$$1$$$。

你的任务是确定吃巧克力棒的顺序,使吃巧克力棒之间的最大休息时间尽可能短。

考虑 Polycarp 在 $$$x$$$ 分钟内吃了一个酒吧,并在 $$$y$$$ 分钟内吃了下一个酒吧 ($$$x < y$$$)。那么休息时间等于 $$$y - x - 1$$$ 分钟。波利卡普没有必要吃掉他拥有的所有金条。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 200\,000$$$, $$$2 \le k \le n$$$) — 工作日的长度(以分钟为单位)以及 Polycarp 在工作日开始时拥有的巧克力棒的数量。

第二行包含长度为 $$$n$$$ 的字符串,由零和一组成。如果字符串中的第 $$$i$$$ 个符号等于 0,则波利卡普在 $$$i$$$ 分钟内没有重要的事情要做,他可以吃一块巧克力。在另一种情况下,波利卡普现在正忙着$$$i$$$,无法吃一块巧克力。可以保证字符串的第一个和最后一个字符等于零,并且波利卡普在这几分钟内总是吃巧克力棒。

输出

打印吃巧克力棒之间可能的最短休息时间(以分钟为单位)。

示例

输入 #1

3 3
010

输出 #1

1

输入 #2

8 3
01010110

输出 #2

3

注意

在第一个示例中,Polycarp 无法在第二分钟内吃掉巧克力棒,因此休息时间等于一分钟。

在第二个示例中,Polycarp 无论如何都会在 $$$1$$$ 分钟和 $$$8$$$ 分钟内吃掉巧克力棒,而且他还需要在 $$$5$$$ 分钟内吃掉巧克力棒,因此最大休息时间将等于 $$$3$$$ 分钟。