题目描述

Description

农夫约翰有N(1≤N≤5000)只牛站成一排，有一些很乖的牛朝前站着．但是有些不乖的牛却朝后站着．农夫约翰需要让所有的牛都朝前站着．幸运的是约翰最近买了一个自动转身机．这个神奇的机器能使K(1≤K≤N)只连续的牛转身． 因为约翰从来都不改变K的价值，请帮助他求出K，使旋转次数M达到最小．同时要求出对应的M.

Input

第1行：整数N.
第2行到第N+1行：第i+l行表示牛j的朝向，F表示朝前，B表示朝后．

Output

一行两个数，分别是K和M，中间用空格隔开

Sample Input

7
B
B
F
B
F
B
B

Sample Output

3 3

HINT

当K=3时神奇的机器旋转3次：(1，2，3)，(3，4，5)，和(5，6，7)

题目分析

暴力怎么写? 枚举K然后n^2暴力反转 但是时间复杂度太高
注意到 你反转区间的数是为了更新一个数之后的k个数的奇偶性 那么 可以用一个滑动区间来维护一个数的前k个数中 有多少数是需要被转身的 这样的话时间复杂度就可以接受了

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,a[5010],can[5010];
char s[5];
int ans=0x7f7f7f7f;
int check(int mid)
{
    memset(can,0,sizeof can);
    int sum=0;
    for(int i=1;i<=n-mid+1;i++)
    {
        sum-=can[max(i-mid,0)];
        if((sum&1)&&!a[i]) can[i]=1,sum++;
        else if(!(sum&1)&&a[i]) can[i]=1,sum++;
    }
    for(int i=n-mid+2;i<=n;i++)
    {
        sum-=can[max(i-mid,0)];
        if((sum&1)&&!a[i]) return 0x7f7f7f7f;
        else if(!(sum&1)&&a[i]) return 0x7f7f7f7f;
    }
    for(int i=1;i<=n;i++) can[0]+=can[i];
    return can[0];
}
int main()
{   
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%s",&s[0]),a[i]=(s[0]=='B')?1:0;
    int tmp=0;
    for(int i=n;i>=1;i--) 
    {
        int nmp=check(i);
        if(ans>=nmp) tmp=i,ans=nmp;
    }
    printf("%d %d",tmp,ans);
    return 0;
}