题目

给定一个长度为 \(2n-1\) 的字符串，问一组使得 \(n\) 个长度不小于 \(n\) 的区间中字母W的个数相等的字母W的个数

分析

首先结论就是 \(\max_{i=1}^n\{cW[i\dots i+n-1]\}\) 一定是合法解

以这组解为基准，左右端点如果向外扩展那么个数一定会更多或者不变，

而此时由于当前字母个数最大，那么将端点移动时仍能保证长度不小于 \(n\)

代码

#include <cstdio>
using namespace std;
const int N=2000011;
int n,s[N],ans; char str[N];
int main(){
	scanf("%d%s",&n,str+1);
	for (int i=1;i<2*n;++i){
		s[i]=s[i-1]+(str[i]=='W');
		if (i>=n&&ans<s[i]-s[i-n]) ans=s[i]-s[i-n];
	}
	return !printf("%d",ans);
}