题意就是给你一个字符串和一个数字k,可以把黑得变成白的,白的变成黑的,问你最少有多少次操作可以使k个黑的连在一起
想的复杂了,我第一开始想到连通块了,两个连通块中有几个白的...巴拉巴拉
用不着,慢慢做题积累经验吧
(我好像想到ac的思路了?好像不太会表达)
在每一段看看连续的k,用前缀和实现,黑的表示1,白的表示0,看看哪一段是最小的(每一段的个数是k个元素)
有个小细节,就是我一开始写的是用memset来初始化,遗憾的超时了,用vector‘来初始化吧,动态的初始n+1为0,快了呢
#include<iostream>
#include<vector>
using namespace std;
int main(){
int T;
cin>>T;
while(T--)
{
int n,k;
scanf("%d%d",&n,&k);
string ch;
vector<int> s(n+1,0);
cin>>ch;
ch=" "+ch;
for(int i=1;i<=n;i++) s[i]=s[i-1]+(ch[i]=='B');
int res=n;
for(int i=k;i<=n;i++)
res=min(res,k-(s[i]-s[i-k]));
printf("%d\n",res);
}
return 0;
}
更多推荐
CF D Black and White Stripe #797 div3
发布评论