从一点开始最多能到多少个满足条件的.从开始点这样的搜索就行,
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
int go[1000000];
int main()
{
int i,j,k;
int t;
int n;
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&k);
for (i=1;i<=n;i++)
scanf("%d",go+i);
go[0]=0;
for (i=2;i<=n;i++)
{
go[i]+=go[i-1];
}
if (go[n]+k>=n)
{
printf("%d\n",n);
continue;
}
int ans=0;
j=1;
i=0;
while (j<=n)
{
//cout<<i<<' '<<j<<' '<<ans<<' '<<go[j]-go[i]<<endl;
if (go[j]-go[i]+k>j-i)
{
j++;
ans=max(ans,j-i);
}
else if (go[j]-go[i]+k==j-i)
{
if (j<n&&go[j+1]-go[j]==1)
{
j++;
//cout<<"one";
ans=max(ans,j-i);
}
else if (j<n)
{
//cout<<"two";
i++;
}
else
{
j++;
//cout<<"three";
}
}
else
i++;
//cout<<i<<' '<<j<<' '<<ans<<endl<<endl;
}
printf("%d\n",ans);
}
}
consecutive
Time Limit: 3000 ms Memory Limit: 65535 kB Solved: 45 Tried: 156
Description
You are given a 01 sequence whose size is n. you can change at most k 0 into 1 in the sequence.
Now I want to know how many consecutive 1 in the sequce at most after you do the change.
Input
The first of input is an integer t which stands for the number of test cases.
for each test case, the first line contains two number n, k ( 1 <= n <= 100000, 0 <= k <= n ).
the next contains n element of the sequence, whose value is 0 or 1.
Output
Output the answer in one line for each test case.
Simple Input
2
4 2
1 0 0 1
4 1
1 0 1 0
Simple Output
4
3
Source