题目链接

Face The Right Way POJ - 3276

思路

$$ 反转问题，用到前缀和优化 $$

时间复杂度

$$ O(N^2) $$

代码

#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 1e4 + 10;

char str[10];
int a[MAXN];
int b[MAXN];
int n;

int gao(int x) {
    memset(b, 0, sizeof b);
    int cnt = 0;
    for (int i = 1; i + x - 1 <= n; i++) {
        b[i] += b[i - 1];
        int w = a[i] + b[i];
        if (w & 1) {
            cnt++;
            b[i]++;
            b[i + x]--;
        }
    }
    for (int i = n - x + 2; i <= n; i++) {
        b[i] += b[i - 1];
        int w = a[i] + b[i];
        if (w & 1) {
            return n + 1;
        }
    }
    return cnt;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", str);
        if (str[0] == 'B') {
            a[i]++;
        }
    }

    int ans1 = 1, ans2 = n + 1;
    for (int i = 1; i <= n; i++) {
        int tmp = gao(i);
        if (tmp < ans2) {
            ans1 = i;
            ans2 = tmp;
        }
    }
    printf("%d %d", ans1, ans2);
    return 0;
}