聊斋(storys)

题目链接：

http://acm.ocrosoft.com/problem.php?id=3820&csrf=tjfBLvtdhbKaa1ah9Far89NIeKl3bTTa

题目描述

某人读完《聊斋志异》，编出这样一道题。题目为：现有男鬼(b)、女鬼(r)、小鬼(w)共n人(n<400)，围站成一环（小鬼可以算是男的也可以算是女的）。从某人开始分别在两边数连续相同性别数（两边的性别可不同），直到第一次发现不同性别为止。当前数的这个人至少要同左右两边中的一方具有相同性别，并算到总数中去。

输入

第1行为人的数目n，第2行为n个字符（只有b，r，w三个情况）。

输出

可找到的连续最大同性别总数。

样例输入

29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

样例输出

11

题解：暴力+模拟。如果开始是一串连续的w，记录下它的数目，直到遇到一串或一个b或r，再把它们的数目加在一起，作为一次可能的结果。如果开始是一个或一串b或r记录下它的数目，直到遇到一个或一串w，把它们的数目加在一起作为一个结果，然后在每个结果中找出最大的即可。因为是围成一个环，所以需要解决头尾连续问题，只需要把所有的元素在数组后面复制一遍。

代码：

#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;



int main()

{

    int n;

    int a=0,b=0,w=0,m=0;

    char c='0';

    char st[1000];

    cin>>n;

    cin>>st;

    memcpy(st+n,st,n);

    int i;

    for(i=0;i<=2*n;i++)

    {

        if(st[i]=='w')

        {

            b++;

            w++;//记录连续w的数目

        }

        else if(st[i]==c)

        {

            b++;//记录前一个b/r连续的数目

            w=0;

        }

        else//此时找的一个结果，开始统计数目

        {

            m=max(a+b,m);//找出最大的

            a=b-w;

            b=w+1;

            w=0;

            c=st[i];//暂时存下需要比较的新的b/r

        }

    }

    m=max(m,a+b);

    m=min(m,n);

    cout<<m;

    return 0;

}