题目：

在幼儿园有n个小朋友排列为一个队伍，从左到右一个挨着一个编号为(0~n-1)。其中有一些是男生，有一些是女生，男生用’B’表示，女生用’G’表示。小朋友们都很顽皮，当一个男生挨着的是女生的时候就会发生矛盾。作为幼儿园的老师，你需要让男生挨着女生或者女生挨着男生的情况最少。你只能在原队形上进行调整，每次调整只能让相邻的两个小朋友交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如：
GGBBG -> GGBGB -> GGGBB
这样就使之前的两处男女相邻变为一处相邻，需要调整队形2次
输入描述:

输入数据包括一个长度为n且只包含G和B的字符串.n不超过50.

输出描述:

输出一个整数，表示最少需要的调整队伍的次数

输入例子:

GGBBG

输出例子:

2

分析：

解：最后矛盾最少的状态只可能是男生和女生分别在两边，最多只有中间一个男生挨着女生，所以总共有两种方式：男生全部在座女生全部在右；女生全部在坐男生全部在右。

算法：所以分两种情况：把男生全部移到左边；把女生全部移到左边。再从两个数中求一个最小值即可。在移动的时候可以用一个游标记录一次需要移动的位置次数，这样会简化移动过程，不需要每次只能移动一步。

算法代码：

int adjustFormation(const char * formation, int size)
{
    bool * formBoyMove = new bool[size];
    bool * formGirlMove = new bool[size];
    
    for (int i = 0; i < size; ++i) {
        if ('B' == formation[i]) {
            formBoyMove[i] = formGirlMove[i] = true;
        } else {
            formBoyMove[i] = formGirlMove[i] = false;
        }
    }
    
    int minChangeTimes, boyMove, girlMove;
    boyMove = girlMove = 0;
    
    int tempChangingTimes = 1;
    
    //move boy
    for (int i = 0; i < size; ++i) {
        if (true == formBoyMove[i]) {
            continue;
        } else {
            //find the closest boy
            while (true != formBoyMove[i+tempChangingTimes] && (tempChangingTimes + i) < size) {
                ++tempChangingTimes;
            }

            //no boys behind
            if (tempChangingTimes + i >= size) {
                //move end
                break;
            }
            
            //change formation for tempChangingTimes
            formBoyMove[i] = true;
            formBoyMove[i+tempChangingTimes] = false;
            boyMove += tempChangingTimes;
            
            //reset tempChangingTimes
            tempChangingTimes = 1;
        }
    }
    
    //reset tempChangingTimes
    tempChangingTimes = 1;
    
    //move girl
    for (int i = 0; i < size; ++i) {
        if (false == formGirlMove[i]) {
            continue;
        } else {
            //find the closest girl
            while (false != formGirlMove[i+tempChangingTimes] && (tempChangingTimes + i) < size) {
                ++tempChangingTimes;
            }
            
            //no girls behind
            if (tempChangingTimes + i >= size) {
                //move end
                break;
            }
            
            //change formation for tempChangingTimes
            formGirlMove[i] = false;
            formGirlMove[i+tempChangingTimes] = true;
            girlMove += tempChangingTimes;
            
            //reset tempChangingTimes
            tempChangingTimes = 1;
        }
    }
    
    minChangeTimes = min(boyMove, girlMove);
    
    return minChangeTimes;
}

测试代码：

//
//  main.cpp
//  adjustFormation
//
//  Created by Jiajie Zhuo on 2017/4/7.
//  Copyright © 2017年 Jiajie Zhuo. All rights reserved.
//

#include <iostream>

#define MAXNUMBER 50

using namespace std;

int adjustFormation(const char * formation, int size);

int main(int argc, const char * argv[]) {
    cout << "Please enter the formation of students: ";
    char * formation = new char[MAXNUMBER];
    cin >> formation;
    
    int size = (int)strlen(formation);
    
    int minChangeTimes = adjustFormation(formation, size);
    cout << "The minimum times of changing is " << minChangeTimes << endl;
    
    delete [] formation;
    
    return 0;
}

总结：

简化问题的关键点即是用一个游标记录下一个男生（女生）的的位置，这样可以一次移动多步。