UESTC 490 Swap Game

た入场券 2022-08-05 07:22 152阅读 0赞

题意：  
有一堆红球白求围了个圈,求用最少的交换次数使得红的白的各自连在一起。  
思路：  
因为是环，因此将整个环变为长度为2n的链，实现循环。  
那么如果是枚举每一个长度为n的片段，再判断的话，时间复杂度为O(n2)，太慢了。  
那么需要将复杂度降低至少到O(nlogn)

因为是环，所以存在一个两个方向都能走的问题，  
首先,假设所有的R全都往最前面移,那么移动的次数就是每一个R前面有多少个B的和（类似逆序数吧） 。这里处理出一个前缀和。  
然后,如果某一个R不动,其余的R都向他靠拢,只考虑一个方向,我们需要在O(1)的时间处理出移动的数,那么对于要移动的每一个R，都多算了第一个R前面有多少个B，这些都是可以在O(1)得到的，也就可以在O(1)求出结果。  
再考虑需要往两个方向移动，对于一个需要移动的R来说，假如它前面需要走过的B超过了B总数的一半，那么它一定会选择往反方向找固定的R汇合，同理更靠后的更加会往反方向走，所以与固定的R间隔一半B以内的直接靠拢，另一半往反方向靠拢，靠拢这个过程的移动次数我们可以在O(1)的时间算出来，那么就可以枚举每一个R做固定点来计算最小花费，考虑B的情况就把R和B反过来再算一次就好了。

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    
    using namespace std;
    
    typedef long long ll;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    #define MID(x,y) (x+((y-x)>>1))
    #define speed std::ios::sync_with_stdio(false);
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define llINF 1ll<<62
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAXN = 100000 * 2 + 5;
    char s[MAXN];
    int a[MAXN];
    
    ll gao(int a[], int n)
    {
        static ll f1L[MAXN], f1R[MAXN], f0L[MAXN], f0R[MAXN];
        static ll gL[MAXN], gR[MAXN];
        f1L[0]=0;
        f0L[0]=0;
        gL[0]=0;
        f1R[2*n+1]=0;
        f0R[2*n+1]=0;
        gR[2*n+1]=0;
        for (int i=1; i<=n+n; i++)
        {
            f1L[i]=(a[i]==1)+f1L[i-1];
            f0L[i]=(a[i]==0)+f0L[i-1];
            gL[i]=gL[i-1]+(a[i]==1 ? f0L[i]:0);
        }
        for (int i=n+n; i>=1; i--)
        {
            f1R[i]=(a[i]==1)+f1R[i+1];
            f0R[i]=(a[i]==0)+f0R[i+1];
            gR[i]=gR[i+1]+(a[i]==1 ? f0R[i]:0);
        }
        int c0=0;
        for (int i=1; i<=n; i++)
            c0+=(a[i]==0);
    // cout << "c0 = " << c0 << endl;
        ll ans=llINF;
        int j=1;
        for(int i=1; i<=n; i++)
        {
            if(a[i]!=1)
                continue;
            while(f0L[j]-f0L[i]<(c0+1)/2)
                j++;
            ll t=gL[j]-gL[i]-(f1L[j]-f1L[i])*f0L[i]+gR[j+1]-gR[i+n]-(f1R[j+1]-f1R[i+n])*f0R[i+n];
    // cout << i << " " << j << " " << i + n << " "<< t << endl;
            ans=min(ans,t);
        }
        return ans;
    }
    
    int main()
    {
        int T,cas=1;
        read(T);
        while(T--)
        {
            scanf("%s",s+1);
            int n=strlen(s+1);
            int totR=0, totB=0;
            for (int i=1; i<=n; i++)
            {
                a[i]=(s[i]=='R');
                if(s[i]=='R')
                    totR++;
                else
                    totB++;
                a[i+n]=a[i];
            }
            if(totR<=1 || totB<=1)
            {
                printf("Case #%d: %lld\n",cas++, 0);
                continue;
            }
            ll ans=llINF;
            ans=min(ans,gao(a,n));
            for(int i=1; i<=n+n; i++)
                a[i]=1-a[i];
            ans=min(ans,gao(a,n));
            printf("Case #%d: %lld\n",cas++, ans);
        }
    }