网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[東方S3]比那名居天子
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | tenshi.in | 输出文件 | tenshi.out |
Problem 1 |
比那名居天子(tenshi.cpp/c/pas) |
题目描述 |
在幻想乡,比那名居天子是管理着『要石』的天人。『要石』是能够引发和镇压地震的存在,当然也可以用来改变地形。因为在幻想乡引发地震,而被灵梦等人教训了之后,天子不得不使用『要石』来修复地面。幻想乡可以视为长度为N个格子的一条横轴,其中有些格子的土地由于地震被破坏(记为1),有些格子则没有(记为0)。每次使用『要石』,可以把一段长度为L的格子全部修复完成(即将1变为0,L覆盖的范围可以超出地图),当然L越大,使用时所花费的灵力也就越多。天子希望最多使用K次『要石』就将所有被破坏的土地全部修复完成(即将1全部变为0),并且花费尽可能小的灵力。她想知道能够达到这个目的的L最小是多少。 |
输入格式 |
第1行:2个整数,N, K 第2行:1个 01 串,长度为 N |
输出格式 |
第1行:1个整数,L 的最小值 |
输入样例 |
10 3 0101111011 |
输出样例 |
3 |
样例解释 |
0101111011 > 0000111011 > 00000000011 > 0000000000 |
数据范围 |
对于 60%的数据:1 ≤ N,K ≤ 5,000 对于 100%的数据:1 ≤ N,K ≤ 500,000 |