【拓展训练】【小信反转串】

#include<bits/stdc++.h>
using namespace std;
int n,k,b[100010],cntb,cntc,c[100010],sum[100010],ans,sum1[100010],idi,idj;
char a[100010];
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]==a[i-1])
{
if(a[i]==‘0’)
{
c[cntc]++;
}
else
{
b[cntb]++;
}
}
else
{
if(a[i]==‘0’) c[++cntc]++;
else b[++cntb]++;
}
}
for(int i=1;i<=n+1;i++)
{
sum[i]=sum[i-1]+c[i];
}
for(int i=1;i<=n+1;i++)
{
sum1[i]=sum1[i-1]+b[i];
}
for(int i=1,j=1;i<=cntc&&j<=cntc;)
{
while(sum[j]-sum[i-1]<=ans&&j<=cntc)
{
j++;
}
if(sum[j]-sum[i-1]>ans&&j-i+1<=k)
{
ans=sum[j]-sum[i-1];
idi=i;
idj=j;
}
if(j-i+1>k)
{
i++;
}
}
if(a[1]==‘0’)
{
cout<<ans+sum1[idj]-sum1[idi-2>0?idi-2:0];
}
else
{
cout<<ans+sum1[idj+1]-sum1[idi-1>0?idi-1:0];
}
return 0;
}

WA 78
4 个赞

这是个双指针题

3 个赞

你看看这个

里面有思路,自己改吧

4 个赞