在幼兒園有n個小朋友排列為一個隊伍，從左到右一個挨著一個編號為(0~n-1)。其中有一些是男生，有一些是女生，男生用'B'表示，女生用'G'表示。
小朋友們都很頑皮，當(dāng)一個男生挨著的是女生的時候就會發(fā)生矛盾。作為幼兒園的老師，你需要讓男生挨著女生或者女生挨著男生的情況最少。
你只能在原隊形上進(jìn)行調(diào)整，每次調(diào)整只能讓相鄰的兩個小朋友交換位置，現(xiàn)在需要盡快完成隊伍調(diào)整，你需要計算出最少需要調(diào)整多少次可以讓上述情況最少。
例如：
GGBBG -> GGBGB -> GGGBB
這樣就使之前的兩處男女相鄰變?yōu)橐惶幭噜?#xff0c;需要調(diào)整隊形2次

分析

最終目標(biāo)是將男孩移到最左邊，或者將女孩移到最左邊。

如果有B個男孩，則移到最左邊的index分別為：0,1,2...B-1,所以所有index的和為（B-1）*B/2

一次遍歷，計算目前男孩所在的index的和為sumB，則sumB減去上面的和就是所求的結(jié)果。

因此只要一次遍歷，計算男孩所在的男孩的個數(shù)和男孩所在的index的和，求之差就行了。女孩同理。最后求最小值。

1 #include <string> 2 #include <iostream> 3 using namespace std; 4 int main(){ 5 string S; 6 cin>>S; 7 int B=0; 8 int G=0; 9 int sumB=0; 10 int sumG=0; 11 for(int i=0;i<S.size();i++){ 12 if(S[i]=='G'){ 13 G++; 14 sumG+=i; 15 } 16 else{ 17 B++; 18 sumB+=i; 19 } 20 } 21 int ret1=sumB-B*(B-1)/2; 22 int ret2=sumG-G*(G-1)/2; 23 int ret=ret1<ret2?ret1:ret2; 24 cout<<ret; 25 return 0; 26 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/D-DZDD/p/7349185.html

總結(jié)

以上是生活随笔為你收集整理的小朋友 排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。