题解 CF1776G 【Another Wine Tasting Event】

· · 题解

这种东西肯定要考虑构造一组特殊解。

考虑尝试把 r - l + 1 \geq n 变成钦定其中某个 r - l + 1 = n，则我们可以得出对应的 x。

我们期待的 [l, r] 肯定也不是随便某一个就行，比如说我们钦定其为 x 最小者。

但我们很快就会发现这样有问题。比如说 x = 0 时，我们可以构造 n 个 R 与 n - 1 个 W 的拼接，然后就寄了……

转而考虑钦定其为 x 最大者，然后我们来考虑如何构造：

显然此时 [l', r'] 均符合长度限制。

前缀和求出 x 即可。时间复杂度为 O(n)。

代码：

#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;
}