[Noip模拟题]寿司

Description
小 c 是一名 oier。最近，他发现他的数据结构好像学傻了。因为他在刷题时碰到了一道傻逼数据结构题，强行使用了平衡树来解决，卡着时间 AC。为此，他被狠狠地嘲讽了一番。于是，小 c 找了大量的数据结构题来做。昨天，小 c 正在吃寿司，突然发现许多盘寿司围成了一个圆圈，这些寿司中有红色的也有蓝色的。由于小 c 看交错的颜色非常不爽，想通过一些操作，使得所有的红色寿司形成了一块连续的区域，蓝色的寿司也形成了一块连续的区域。如果小 c 每次只可以交换相邻的两盘寿司，那么最少需要多少步才可以达到小 c 的要求呢？由于他做题做多了，脑袋已经有点不清醒了，于是这个问题就交给你了。

Input
第一行一个数 T，T<=10表示数据组数。
接下来 T 行，每行一行由 B 和 R 组成的字符串，长度<=1000000，B 表示蓝色， R 表示红色。第 i 个字符描述顺时针数第 i 盘寿司的颜色。注意，最后一盘寿司和第 1 盘寿司是相邻的。

Output
对于每组数据，输出一行表示最小的交换次数。

Sample Input
1
BBRBBRBBBRRR

Sample Output
5

HINT
Sol

标准题解请点击这里

自己的题解（part 1）
上面的标准题解我几乎没有看懂……
然后就开始乱搞。
首先，把样例画出来：

可以看出，选择一个点，将与它同颜色的点向它靠近，这样是较优的方案。
而向它靠近的方式，显然是在它左侧的点靠近后在它左侧，在它右侧的点靠近后也在它的右侧。
那么时间复杂度为O(t∗len2)的算法就出来了：
枚举每一个中心点，然后枚举其他与它同颜色的点是向它左侧靠还是向它右侧靠近。

O(t∗len2)代码

#include <cstdio>
#include <cstring>

const int maxn=1000000;
const int inf=2000000000;

int t,len;
char s[maxn+10];

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s);
        len=strlen(s);
        int ans=inf;
        for(int i=0; i<len; i++)
        //枚举中心点
        {
            int sum=0;
            int nowl=i,cntl=0;
            int nowr=i,cntr=0;
            for(int j=1; j<=(len+1)/2-1; j++)
            //寻找在中心点左侧的点
            {
                nowl--;
                int now=nowl;
                if(now<0)
                {
                    now=(now+len)%len;
                }
                if(s[now]==s[i])
                {
                    cntl++;
                    sum+=i-nowl-cntl;
                }
            }
            for(int j=1; j<=(len+1)/2-1; j++)
            //枚举在中心点右侧的点
            {
                nowr++;
                int now=nowr;
                if(now>=len)
                {
                    now%=len;
                }
                if(s[now]==s[i])
                {
                    cntr++;
                    sum+=nowr-i-cntr;
                }
            }
            if(!(len&1))
            //讨论正对中心点的点
            {
                if(s[i]==s[(i+len/2)%len])
                {
                    if(cntl>cntr)
                    {
                        cntl++;
                        sum+=len/2-cntl;
                    }
                    else
                    {
                        cntr++;
                        sum+=len/2-cntr;
                    }
                }
            }
            if(sum<ans)
            {
                ans=sum;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

自己的题解（part 2）
看了上面的思路，我们可以发现，每个中心点左侧和右侧的点的数量（包括红色点和蓝色点）都是相同的，而中心点之间又有很多重复之处，那么我们可以想到优化方法了：队列。预处理，用两个队列存储每个点作为中心点时，左侧或右侧的点区要想使某种颜色集中在某一侧，所需要花费的代价。那么每个点就使用已经算出来的数据在O(1)的时间复杂度内得出解，总时间复杂度O(t∗len)。

O(t∗len)代码

#include <cstdio>
#include <cstring>

const int maxn=1000000;
const long long inf=200000000000;

int t,len,a[maxn+10];
long long f[2][2][maxn+10];
long long cnt[2][2][maxn+10];
char s[maxn+10];

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0,sizeof f);
        memset(cnt,0,sizeof cnt);
        scanf("%s",s);
        len=strlen(s);
        for(int i=0; i<len; i++)
        {
            if(s[i]=='R')
            {
                a[i]=0;
            }
            else
            {
                a[i]=1;
            }
        }
        long long ans=inf;
        for(int i=0; i<=(len+1)/2-2; i++)
        //首先处理(len-1)号点作中心点时移动左侧的点的花费
        {
            cnt[0][a[i]][0]++;
            f[0][a[i]][0]+=i-cnt[0][a[i]][0]+1;
        }
        for(int i=1; i<len; i++)
        //再用队列优化处理0~(len-2)作中心点时左侧点的花费的方式
        {
            cnt[0][0][i]=cnt[0][0][i-1];
            cnt[0][1][i]=cnt[0][1][i-1];
            cnt[0][a[i-1]][i]--;
            f[0][0][i]=f[0][0][i-1];
            f[0][1][i]=f[0][1][i-1];
            f[0][1-a[i-1]][i]-=cnt[0][1-a[i-1]][i];
            cnt[0][a[(i+(len+1)/2-2)%len]][i]++;
            f[0][a[(i+(len+1)/2-2)%len]][i]+=(len+1)/2-1-cnt[0][a[(i+(len+1)/2-2)%len]][i];
        }
        for(int i=len-1; i>=len-(len-1)/2; i--)
        //处理出0号点作中心点时移动右侧的点花费的代价
        {
            cnt[1][a[i]][len-1]++;
            f[1][a[i]][len-1]+=len-i-cnt[1][a[i]][len-1];
        }
        for(int i=len-2; i>=0; i--)
        //再用队列优化处理1~(len-1)作中心点时移动右侧点的计算方式
        {
            cnt[1][0][i]=cnt[1][0][i+1];
            cnt[1][1][i]=cnt[1][1][i+1];
            cnt[1][a[i+1]][i]--;
            f[1][0][i]=f[1][0][i+1];
            f[1][1][i]=f[1][1][i+1];
            f[1][1-a[i+1]][i]-=cnt[1][1-a[i+1]][i];
            cnt[1][a[(i-(len+1)/2+2+len)%len]][i]++;
            f[1][a[(i-(len+1)/2+2+len)%len]][i]+=(len+1)/2-1-cnt[1][a[(i-(len+1)/2+2+len)%len]][i];
        }
        for(int i=0; i<len; i++)
        //枚举每个点作中心点时的情况
        {
            long long sum=f[0][a[i]][(i+1)%len]+f[1][a[i]][(i-1+len)%len];
            //sum就是左侧的点与右侧点向中心点移动花费的距离之和
            if(!(len&1))
            //最后讨论正对中心点的点
            {
                if(a[i]==a[(i+len/2)%len])
                {
                    if(cnt[0][a[i]][(i+1)%len]>cnt[1][a[i]][(i-1+len)%len])
                    {
                        sum+=len/2-cnt[0][a[i]][(i+1)%len];
                    }
                    else
                    {
                        sum+=len/2-cnt[1][a[i]][(i-1+len)%len];
                    }
                }
            }
            if(sum<ans)
            //更新ans
            {
                ans=sum;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}