問(wèn)題描述
在幼兒園有n個(gè)小朋友排列為一個(gè)隊(duì)伍仰冠，從左到右一個(gè)挨著一個(gè)編號(hào)為(0~n-1)。其中有一些是男生蝶糯，有一些是女生洋只，男生用'B'表示，女生用'G'表示昼捍。小朋友們都很頑皮识虚，當(dāng)一個(gè)男生挨著的是女生的時(shí)候就會(huì)發(fā)生矛盾。作為幼兒園的老師妒茬，你需要讓男生挨著女生或者女生挨著男生的情況最少担锤。你只能在原隊(duì)形上進(jìn)行調(diào)整，每次調(diào)整只能讓相鄰的兩個(gè)小朋友交換位置乍钻，現(xiàn)在需要盡快完成隊(duì)伍調(diào)整肛循，你需要計(jì)算出最少需要調(diào)整多少次可以讓上述情況最少。例如：
GGBBG -> GGBGB -> GGGBB
這樣就使之前的兩處男女相鄰變?yōu)橐惶幭噜徱瘢枰{(diào)整隊(duì)形2次
輸入描述
輸入數(shù)據(jù)包括一個(gè)長(zhǎng)度為n且只包含G和B的字符串.n不超過(guò)50.
輸出描述
輸出一個(gè)整數(shù)多糠，表示最少需要的調(diào)整隊(duì)伍的次數(shù)
輸入例子
GGBBG
輸出例子
2
分析
初看起來(lái)和逆序?qū)Φ膯?wèn)題很像，逆序?qū)梢栽诟鞣N排序算法中進(jìn)行統(tǒng)計(jì)欢摄。但是題目要求男生和女生只能和相鄰的小朋友交換位置熬丧，不能和隊(duì)伍中的任何一個(gè)人交換位置笋粟。于是想到two-pointers的方法怀挠，首尾指針遍歷析蝴，遇到順序不對(duì)的就進(jìn)行交換，累加計(jì)數(shù)器绿淋。注意最終的結(jié)果可能是GGG...BBB...闷畸，也可能是BBB...GGG...，兩種情況都需要考慮吞滞，最后取交換次數(shù)較小的那個(gè)佑菩。
note
不需要真正交換元素，遍歷到順序不對(duì)的元素只累加計(jì)數(shù)器就好了
代碼
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
// 計(jì)算交換次數(shù)裁赠，bc(begin character)為隊(duì)首性別殿漠，ec(end character)為隊(duì)尾性別
int calcSwapCount(char bc, char ec, char *str, int n)
{
int count = 0;
int begin = 0, end = n - 1;
while (begin < end)
{
if (str[begin] == bc)
begin++;
else if (str[end] == ec)
end--;
else if (str[begin] == ec && str[end] == bc)
{
count += end - begin; // 將順序出錯(cuò)的begin和end交換需要的步數(shù)
begin++;
end--;
}
}
return count;
}
int main()
{
char str[51];
scanf("%s", &str);
int n = strlen(str);
printf("%d\n", min(calcSwapCount('G', 'B', str, n),
calcSwapCount('B', 'G', str, n)));
return 0;
}
