首页 > 试题广场 >

换座位

[编程题]换座位
  • 热度指数:243 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛家村准备开会选举新任村长,村长安排了一个位置表Position(桌子是圆桌!!!所以第一个人和最后一个人是挨着坐的)。村长的候选人牛牛,牛妹,牛大三个。
为了让选举进行的更加顺利,村长想让三位的支持者分别坐在一起 他想知道最少多少人需要换座位才能使得三类支持者都分别坐在一起。
返回一个整数代表最少多少人需要换座位才能使得三类支持者都分别坐在一起。

示例1

输入

[1,2,2,1,3]

输出

2

说明

将最后一个人与倒数第二个人的位置互换

备注:
给定 Table数组

1代表牛牛阵营,2代表牛大阵营,3代表牛妹阵营
class Solution {
public:
    /**
     * 
     * @param Position int整型一维数组 
     * @param PositionLen int Position数组长度
     * @return int整型
     */
    int F(int *Position, map<int,int> M, int *a){
        int k=0, cnt=0, Min=0;
        for(int i=0;i<3;i++){
            for(int j=0;j<M[a[i]];j++){
                if(Position[k]!=a[i])
                    cnt++;
                k++;
            }
        }
        Min = cnt;
        int x=M[a[0]]-1, y=x+M[a[1]], z=y+M[a[2]];
        for(;x>0;x--,y--,z--){
            if(Position[x]==a[0])
                cnt++;
            else if(Position[x]==a[1])
                cnt--;
            if(Position[y]==a[1])
                cnt++;
            else if(Position[y]==a[2])
                cnt--;
            if(Position[z]==a[2])
                cnt++;
            else if(Position[z]==a[0])
                cnt--;
            Min = min(Min, cnt);
        }
        return Min;
    }
    int ChangePosition(int* Position, int PositionLen) {
        map<int,int> M;
        for(int i=0;i<PositionLen;i++)
            M[Position[i]]++;
        int L[6][3] = {{1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}};
        int Min=INT_MAX;
        for(int i=0;i<6;i++){
            int s = F(Position, M, L[i]);
            Min = min(Min, s);
        }
        return Min;
    }
};

发表于 2020-08-27 15:26:34 回复(0)