[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=;
const int inf=;

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

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s);
        len=strlen(s);
        int ans=inf;
        for(int i=; i<len; i++)
        //枚舉中心點
        {
            int sum=;
            int nowl=i,cntl=;
            int nowr=i,cntr=;
            for(int j=; j<=(len+)/-; j++)
            //尋找在中心點左側的點
            {
                nowl--;
                int now=nowl;
                if(now<)
                {
                    now=(now+len)%len;
                }
                if(s[now]==s[i])
                {
                    cntl++;
                    sum+=i-nowl-cntl;
                }
            }
            for(int j=; j<=(len+)/-; j++)
            //枚舉在中心點右側的點
            {
                nowr++;
                int now=nowr;
                if(now>=len)
                {
                    now%=len;
                }
                if(s[now]==s[i])
                {
                    cntr++;
                    sum+=nowr-i-cntr;
                }
            }
            if(!(len&))
            //讨論正對中心點的點
            {
                if(s[i]==s[(i+len/)%len])
                {
                    if(cntl>cntr)
                    {
                        cntl++;
                        sum+=len/-cntl;
                    }
                    else
                    {
                        cntr++;
                        sum+=len/-cntr;
                    }
                }
            }
            if(sum<ans)
            {
                ans=sum;
            }
        }
        printf("%d\n",ans);
    }
    return ;
}
           

自己的題解（part 2）

看了上面的思路，我們可以發現，每個中心點左側和右側的點的數量（包括紅色點和藍色點）都是相同的，而中心點之間又有很多重複之處，那麼我們可以想到優化方法了：隊列。預處理，用兩個隊列存儲每個點作為中心點時，左側或右側的點區要想使某種顔色集中在某一側，所需要花費的代價。那麼每個點就使用已經算出來的資料在 O(1) 的時間複雜度内得出解，總時間複雜度 O(t∗len) 。

O(t∗len) 代碼

#include <cstdio>
#include <cstring>

const int maxn=;
const long long inf=;

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

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(f,,sizeof f);
        memset(cnt,,sizeof cnt);
        scanf("%s",s);
        len=strlen(s);
        for(int i=; i<len; i++)
        {
            if(s[i]=='R')
            {
                a[i]=;
            }
            else
            {
                a[i]=;
            }
        }
        long long ans=inf;
        for(int i=; i<=(len+)/-; i++)
        //首先處理(len-1)号點作中心點時移動左側的點的花費
        {
            cnt[][a[i]][]++;
            f[][a[i]][]+=i-cnt[][a[i]][]+;
        }
        for(int i=; i<len; i++)
        //再用隊列優化處理0~(len-2)作中心點時左側點的花費的方式
        {
            cnt[][][i]=cnt[][][i-];
            cnt[][][i]=cnt[][][i-];
            cnt[][a[i-]][i]--;
            f[][][i]=f[][][i-];
            f[][][i]=f[][][i-];
            f[][-a[i-]][i]-=cnt[][-a[i-]][i];
            cnt[][a[(i+(len+)/-)%len]][i]++;
            f[][a[(i+(len+)/-)%len]][i]+=(len+)/--cnt[][a[(i+(len+)/-)%len]][i];
        }
        for(int i=len-; i>=len-(len-)/; i--)
        //處理出0号點作中心點時移動右側的點花費的代價
        {
            cnt[][a[i]][len-]++;
            f[][a[i]][len-]+=len-i-cnt[][a[i]][len-];
        }
        for(int i=len-; i>=; i--)
        //再用隊列優化處理1~(len-1)作中心點時移動右側點的計算方式
        {
            cnt[][][i]=cnt[][][i+];
            cnt[][][i]=cnt[][][i+];
            cnt[][a[i+]][i]--;
            f[][][i]=f[][][i+];
            f[][][i]=f[][][i+];
            f[][-a[i+]][i]-=cnt[][-a[i+]][i];
            cnt[][a[(i-(len+)/++len)%len]][i]++;
            f[][a[(i-(len+)/++len)%len]][i]+=(len+)/--cnt[][a[(i-(len+)/++len)%len]][i];
        }
        for(int i=; i<len; i++)
        //枚舉每個點作中心點時的情況
        {
            long long sum=f[][a[i]][(i+)%len]+f[][a[i]][(i-+len)%len];
            //sum就是左側的點與右側點向中心點移動花費的距離之和
            if(!(len&))
            //最後讨論正對中心點的點
            {
                if(a[i]==a[(i+len/)%len])
                {
                    if(cnt[][a[i]][(i+)%len]>cnt[][a[i]][(i-+len)%len])
                    {
                        sum+=len/-cnt[][a[i]][(i+)%len];
                    }
                    else
                    {
                        sum+=len/-cnt[][a[i]][(i-+len)%len];
                    }
                }
            }
            if(sum<ans)
            //更新ans
            {
                ans=sum;
            }
        }
        printf("%lld\n",ans);
    }
    return ;
}