换座位题解

解法1：
最后无论如何，一定是牛牛的人坐在一起，牛妹的人坐在一起，牛大的人坐在一起。假设我们把牛牛，牛妹，牛大人用代替。因为是圆桌那么最后从某个点开始一定可以是 这样的
那么我们可以枚举起点，枚举哪一个点作为第一个的位置，由于出现了多少次我们是知道的，那么最后一个的位置我们也获得到了，我们只需要知道从里面有多少有多少，这个用前缀和维护就好了。那么这些是不用动的，其余的就是需要换位置的。接着我们枚举旁边是还是，并分别计算答案，计算，需要换位置的人数的方式同。
时间复杂度,空间复杂度。

class Solution {
public:
    /**
     * 
     * @param Position int整型一维数组 
     * @param PositionLen int Position数组长度
     * @return int整型
     */
    int a[210000],b[210000],c[210000],pos[210000];
    int ChangePosition(int* Position, int PositionLen) {
        // write code here
        int n=PositionLen;
        for(int i=1;i<=n;i++) pos[i]=Position[i-1];
        for(int i=1;i<=n;i++) pos[i+n]=pos[i];
        for(int i=1;i<=2*n;i++) {
            a[i]=a[i-1];
            b[i]=b[i-1];
            c[i]=c[i-1];
            if(pos[i]==1) a[i]++;
            else if(pos[i]==2) b[i]++;
            else c[i]++;
        }
        int A=a[n],B=b[n],C=c[n];
        int ans=1e9;
        for(int i=1;i<=n;i++) {//枚举a的起始位置
            int movea=A-(a[i+A-1]-a[i-1]);
            //假设右边的是b
            int j=i+A;
            int moveb=B-(b[j+B-1]-b[j-1]);
            int k=j+B;
            int movec=C-(c[k+C-1]-c[k-1]);
            ans=min(ans,movea+moveb+movec);
            //假设右边的是c
            j=i+A;
            movec=C-(c[j+C-1]-c[j-1]);
            k=j+C;
            moveb=B-(b[k+B-1]-b[k-1]);
            ans=min(ans,movea+moveb+movec);
        }
        return ans;
    }
};

解法2：TLE
我们枚举每一个人换完位置后的位置。统计有多少个人不是坐在之前自己的位置上，并且判断三类人是不是坐在一起的即可。枚举换完位置后的位置可以用全排列来做。时间复杂度，空间复杂度。

class Solution {
public:
    /**
     * 
     * @param Position int整型一维数组 
     * @param PositionLen int Position数组长度
     * @return int整型
     */
    int a[210000],b[210000],c[210000],pos[210000];
    int ChangePosition(int* Position, int PositionLen) {
        // write code here
        int n=PositionLen;
        for(int i=1;i<=n;i++) pos[i]=Position[i-1],a[i]=i;
        int ans=1e9;vector<int>v;
        do {
            int flag=0,tot=0;
            v.clear();
            for(int i=1;i<=n;i++) {
                int id=a[i];
                if(id!=i) tot++;
                v.push_back(pos[id]);
            }
            v.erase(unique(v.begin(),v.end()),v.end());
            if(v.size()<=3||(v.size()==4&&v[0]==v[3])) flag=1;
            if(flag) ans=min(ans,tot);
        }while(next_permutation(a+1,a+1+n));
        return ans;
    }
};