CDOJ 490 UESTC 490 Swap Game（思路，逆序对）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：有两种颜色的小球形成环，求最小交互次数使球相连。

题解：先解决另一个简单的问题，如果是一个链，把红球标记为1，蓝球标记为0，要排成升序需要多少次交换呢？答案是逆序对总数，原因是一次交互最多消除一个逆序对，而且有策略可以保证每次消除一个逆序对。要解决这个问题，需要做一些变通。看蓝球，因为是环，为了使交换次数最小，前半段的蓝球应该往前靠，所以在后半段的蓝球应该往后靠。那么就把原序列划分成两半，前面一段记红球为1，蓝球为0，后面一段记蓝球为1，红球为0，然后分别计算逆序对数，就可以求出以0位置前为中心的逆序数。然后在枚举中心的位置，枚举的时候，可以在O(1)时间计算出新的逆序值，具体方法是只考虑端点处的小球对左右区间逆序值的影响。

记左区间长度为b1，把中心移动到b1+i球的后面，那么b1+i位置的球会加入左区间，i号球则加入到右区间，当b1+i号球是R的时候，它对左右两边的逆序值都是没有影响的，(对于右区间，R是0，对于左区间，R是1)，当它是B的时候，对于右区间，逆序对总数减少了原来右区间中0的个数，对于左区间，增加了i移动之后1的个数。对于i的移动，类似地讨论一下。

#include<cstdio>

#include<cmath>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

//#define local

const int maxn = 1e5+;

int C[];

char str[maxn];

int main()

{

#ifdef local

    freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

#endif // local

    int T;

    scanf("%d",&T);getchar();

    for(int k = ; k <= T; k++){

        printf("Case #%d: ",k);

        gets(str);

        memset(C,,sizeof(C));

        int len = strlen(str);

        int invSum  = ;

        int b1 = len>>,b2 = len - b1;

        for(int i = ; i < b1; i++) {

            if(str[i] == 'R') { C[]++;}

            else { invSum += C[]; }

        }

        for(int i = b1; i < len; i++) {

            if(str[i] == 'B') {  C[]++;}

            else { invSum += C[]; }

        }

        int best = invSum;

        //printf("%d\n",best);

        for(int i = ; i < len; i++){

            int t = (b1+i)%len;

            if(str[t] == 'B') { invSum -= b2-C[]; invSum += C[]- (str[i] == 'R'); }

            if(str[i] == 'R' ) { invSum -= b1-C[]; invSum += C[] - (str[t] == 'B'); }

            if(str[t] == 'B') C[]--;

            else C[]++;

            if(str[i] == 'R') C[]--;

            else C[]++;

            best = min(invSum,best);

        }

        printf("%d\n",best);

    }

    return ;

}