- 魔法
(magic.cpp)
【题目描述】
有一条长度为 N 个格子的横轴土地,其中有些格子的土地由于地震被破坏(记为1),有些格子则没有(记为0)。每次使用魔法,可以把一段长度为L的格子全部修复完成(即将1变为0,L覆盖的范围可以超出地图),当然L越大,使用时所花费的法力也就越多。现在希望最多使用K次魔法将所有被破坏的土地全部修复完成(即将1全部变为0),并且花费尽可能小的法力。我们想知道能够达到这个目的的L值最小是多少?
【输入格式】
第一行包含两个整数,N, K,含义如题意所述。
第二行包含一个长度为N的01 串。
【输出格式】
输出包含一行一个整数,表示L的最小值。
【样例输入输出】
样例输入(magic.in) 样例输出(magic.out)
10 3
0101111011 3
【样例解释】
0101111011 → 0000111011 → 00000000011 → 0000000000
【数据规模】
对于100%的数据:1 ≤ N,K ≤ 5,000,000