题解 CF1776G 【Another Wine Tasting Event】
Leasier
2023-03-25 12:34:06
这种东西肯定要考虑构造一组特殊解。
考虑尝试把 $r - l + 1 \geq n$ 变成钦定其中某个 $r - l + 1 = n$，则我们可以得出对应的 $x$。
我们期待的 $[l, r]$ 肯定也不是随便某一个就行，比如说我们钦定其为 $x$ 最小者。
但我们很快就会发现这样有问题。比如说 $x = 0$ 时，我们可以构造 $n$ 个 `R` 与 $n - 1$ 个 `W` 的拼接，然后就寄了……
转而考虑钦定其为 $x$ 最大者，然后我们来考虑如何构造：
- $\forall 1 \leq l' < l$，指派一个 $r' \leq r$ 即可。
- $\forall r < r' \leq 2n - 1$，指派一个 $l' \geq l$ 即可。
显然此时 $[l', r']$ 均符合长度限制。
前缀和求出 $x$ 即可。时间复杂度为 $O(n)$。
代码：
```cpp
#include <stdio.h>
int sum[2000007];
char s[2000007];
inline int max(int a, int b){
return a > b ? a : b;
}
int main(){
int n, m, ans = 0;
scanf("%d", &n);
scanf("%s", &s[1]);
m = n * 2 - 1;
for (int i = 1; i <= m; i++){
sum[i] = sum[i - 1] + (s[i] == 'W' ? 1 : 0);
}
for (int i = 1; i <= n; i++){
ans = max(ans, sum[i + n - 1] - sum[i - 1]);
}
printf("%d", ans);
return 0;
}
```