问题标题: 酷町堂：1364 打地鼠（mouse）

1364   打地鼠（mouse）

题目描述 Description

打地鼠的游戏大家应该都玩过或听说过，每当有地鼠露头，我们要在规定时间内消灭它！ 作为一支经过特殊训练的地鼠团队，他们能够整齐地站成一排，增加你消灭它们的难度。假如在一排N个空格中（可以想象成长为 N的横轴），有的地鼠已经露头了（记为1），有的没有露头（记为0），幸好你有一个神秘的木板，每次可以把连续的L个地鼠消灭（即将 1 变为 0，L 覆盖的范围可以超出横轴），当然 L 越大，使用时所花费的力气也就越多。希望最多使用 K 次神秘木板就将所有露头地鼠全部消灭(即将1全部变为 0)，并且花费尽可能小的力气。我们想知道能够达到这个目的的L最小是多少。

输入描述 Input Description

输入有2行；
第1行：2个整数，n,k
第2行：1个01串，长度为n

输出描述 Output Description

1个整数，L的最小值

样例输入 Sample Input

10 3
0101111011

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

【样例说明】
0101111011->0000111011->0000000011->0000000000
【数据范围】
对于60%的数据：1<=n,k<=5000
对于100%的数据：1<=n,k<=500000

数据来源 Source

2017包河区省赛前模拟（小学组）

http://judge.codingtang.com/problem/1364/

关键是

只有95分，请看代码（写的有点儿乱）
#include<iostream>
using namespace std;
char a[500001]; 
long long int n,k;
long long int judge(int x) 
{
int i,num=0;
for(i=1;i<=n;i++)
{
if(a[i]=='1')
{
 num++;
 i=i+x-1;
}       
}
if(num>k)
return 1;
else return 0;
}
void read()
{
long long int  i,j,Left,right,mid;
cin>>n>>k; 
for(i=1;i<=n;i++)//hello
cin>>a[i];
a[n+1]='\0';
Left=1;right=(n/k)+1;
while(Left<right)
{ mid=(Left+right)/2;
if(judge(mid)==1)
Left=mid+1; 
else right=mid;
}
cout<<Left<<endl;
} 
int main()
{
read();
return 0;
}

请大家帮忙看看哪里错了

尹宗鑫在2019-02-15 15:20:30追加了内容

试过了，还是95分

1364   打地鼠（mouse）

Wrong Answer:95分

尹宗鑫的测评结果：

测试点#1测评结果 : Accepted时间 : 0ms
测试点#2测评结果 : Accepted时间 : 0ms
测试点#3测评结果 : Accepted时间 : 0ms
测试点#4测评结果 : Accepted时间 : 0ms
测试点#5测评结果 : Accepted时间 : 0ms
测试点#6测评结果 : Accepted时间 : 0ms
测试点#7测评结果 : Accepted时间 : 8ms
测试点#8测评结果 : Wrong Answer时间 : 0ms偷看一下数据测试点#9测评结果 : Accepted时间 : 0ms
测试点#10测评结果 : Accepted时间 : 0ms
测试点#11测评结果 : Accepted时间 : 4ms
测试点#12测评结果 : Accepted时间 : 12ms
测试点#13测评结果 : Accepted时间 : 16ms
测试点#14测评结果 : Accepted时间 : 36ms
测试点#15测评结果 : Accepted时间 : 32ms
测试点#16测评结果 : Accepted时间 : 0ms
测试点#17测评结果 : Accepted时间 : 0ms
测试点#18测评结果 : Accepted时间 : 0ms
测试点#19测评结果 : Accepted时间 : 0ms
测试点#20测评结果 : Accepted时间 : 0ms

我的提交(cpp)：

#include<iostream>
using namespace std;
char a[5500001]; 
long long int n,k;
long long int judge(int x) 
{
int i,num=0;
for(i=1;i<=n;i++)
{
if(a[i]=='1')
{
 num++;
 i=i+x-1;
}       
}
if(num>k)
return 1;
else return 0;
}
void read()
{
long long int  i,j,Left,right,mid;
cin>>n>>k; 
for(i=1;i<=n;i++)//hello
cin>>a[i];
a[n+1]='\0';
Left=1;right=(n/k)+1;
while(Left<right)
{ mid=(Left+right)/2;
if(judge(mid)==1)
Left=mid+1; 
else right=mid;
}
cout<<Left<<endl;
} 
int main()
{
read();
return 0;
}