6.26cf simulation game d: black and white questions

Title Description

link

6.26CF Simulation game D topic

A word description

D. Black and white bar
time limit per test2 s.
memory limit per test256 MB
inputstandard input
outputstandard output
You have a stripe of checkered paper of length n. Each cell is either white or black.

You have a length of n The checkered paper . Each square is dyed white or black .

What is the minimum number of cells that must be recolored from white to black in order to have a segment of k consecutive black cells on the stripe?

If we want to get a continuation on this piece of checkerboard k A black grid , We should at least re dye a few white plaids into black plaids ？

If the input data is such that a segment of k consecutive black cells already exists, then print 0. If there is already a continuous section on this checkered paper k A black grid , Output 0.

Input
The first line contains an integer t (1≤t≤104) — the number of test cases.

The first line contains an integer t (1≤t≤104) — Number of representative test data groups .

Next, descriptions of t test cases follow.

Here are t Group test data .

The first line of the input contains two integers n and k (1≤k≤n≤2⋅105). The second line consists of the letters ‘W’ (white) and ‘B’ (black). The line length is n.

The first line contains two integers n and k (1≤k≤n≤2⋅105). The second line contains n Letters ‘W’ ( white ) and ‘B’ ( black ).

It is guaranteed that the sum of values n does not exceed 2⋅105.

Data assurance n The sum does not exceed 2⋅10^5.

Output
For each of t test cases print an integer — the minimum number of cells that need to be repainted from white to black in order to have a segment of k consecutive black cells.

Each set of test data outputs an integer representing the answer .

Example
inputCopy
4
5 3
BBWBW
5 5
BBWBW
5 1
BBWBW
1 1
W
outputCopy
1
2
0
1
Note
In the first test case, s=“BBWBW” and k=3. It is enough to recolor s3 and get s=“BBBBW”. This string contains a segment of length k=3 consisting of the letters ‘B’.

For the first set of samples ,s=“BBWBW” And k=3, Only will s3 You can get it by dyeing it black s=“BBBBW”. This string contains consecutive k=3 individual ‘B’.

In the second test case of the example s=“BBWBW” and k=5. It is enough to recolor s3 and s5 and get s=“BBBBB”. This string contains a segment of length k=5 consisting of the letters ‘B’. For the second set of examples s=“BBWBW” And k=5, Need to put s3 and s5 obtain s=“BBBBB”. The results include k=5 individual ‘B’.

In the third test case of the example s=“BBWBW” and k=1. The string s already contains a segment of length k=1 consisting of the letters ‘B’.

For the third set of samples ,s The requirements have been met .

Topic analysis

1. To make k individual B All possible cases in succession are n-k+1 Kind of （ From the first place 1 To n-k+1）
2. We just need to know this n-k+1 How many are there in the species W, Taking the minimum value is the final answer
3. There is an algorithm that supports O(n) Algorithm of time complexity , The prefix and
4. The first i Bit start length is k The string of is f[i+k-1]-f[i-1] individual W

Code implementation

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;
int t,n,k,ans;
char a[maxn];	
int f[maxn];
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		ans=maxn;
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++){
    
			scanf(" %c",&a[i]);
			f[i]=f[i-1];
			if(a[i]=='W')f[i]++;
		}
		for(int i=1;i<=n-k+1;i++){
    
			int x=f[i+k-1]-f[i-1];
			ans=min(ans,x);
		}
		printf("%d\n",ans);
	}
	return 0;
}