首页 > 试题广场 >

调整队形

[编程题]调整队形
  • 热度指数：4586 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
在幼儿园有n个小朋友排列为一个队伍，从左到右一个挨着一个编号为(0~n-1)。其中有一些是男生，有一些是女生，男生用'B'表示，女生用'G'表示。小朋友们都很顽皮，当一个男生挨着的是女生的时候就会发生矛盾。作为幼儿园的老师，你需要让男生挨着女生或者女生挨着男生的情况最少。你只能在原队形上进行调整，每次调整只能让相邻的两个小朋友交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如：
GGBBG -> GGBGB -> GGGBB
这样就使之前的两处男女相邻变为一处相邻，需要调整队形2次

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


输出描述:
输出一个整数，表示最少需要的调整队伍的次数
示例1

输入

GGBBG

输出

2
算法知识视频讲解
添加回答
于晨晨头像 于晨晨

最终目标是将男孩移到最左边，或者将女孩移到最左边。

如果有B个男孩，则移到最左边的index分别为：0,1,2...B-1,所以所有index的和为（B-1）*B/2

一次遍历，计算目前男孩所在的index的和为sumB，则sumB减去上面的和就是所求的结果。

因此只要一次遍历，计算男孩所在的男孩的个数和男孩所在的index的和，求之差就行了。女孩同理。最后求最小值。

#include <string>
#include <iostream>
using namespace std;
int main(){
    string S;
    cin>>S;
    int B=0;
    int G=0;
    int sumB=0;
    int sumG=0;
    for(int i=0;i<S.size();i++){
        if(S[i]=='G'){
            G++;
            sumG+=i;
        }
        else{
            B++;
            sumB+=i;
        }
    }
    int ret1=sumB-B*(B-1)/2;
    int ret2=sumG-G*(G-1)/2;
    int ret=ret1<ret2?ret1:ret2;
    cout<<ret;
    return 0;
}
发表于 2017-03-26 20:48:35 回复(13)
南邮陈丹伟头像 南邮陈丹伟 

	import java.util.Scanner;





	







	public class shs {





	







	 public static void main(String[] args) {





	 // TODO Auto-generated method stub





	 Scanner scan = new Scanner(System.in);





	 String s = scan.nextLine();





	 int b=0;





	 int g=0;





	 int bsum = 0;





	 int gsum = 0;





	 for(int i=0;i<s.length();i++){





	 if(s.charAt(i) == 'G'){





	 gsum+=(i-g);





	 g++;





	 }else if(s.charAt(i) == 'B'){





	 bsum+=(i-b);





	 b++;





	 }





	 }





	 





	 System.out.println(Math.min(bsum, gsum));





	 }





	







	}

发表于 2017-03-27 15:29:52 回复(5)
SamChen头像 SamChen 
#include<iostream>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<queue>
#include<algorithm>
 
using namespace std;
 
int main()
{
    vector<char> line;
    int minMoveLeft = 0, leftG = 0;
    int minMoveRight = 0, rightG = 0;
    int minMove = 0;
    char temp = ' ', rightTemp = ' ';
    temp = getchar();
    while (temp == 'G' || temp == 'B')
    {
        line.push_back(temp);
        temp = getchar();
    }
    for (size_t i = 0; i < line.size(); i++)
    {
        temp = line[i];
        rightTemp = line[line.size()-1-i];
        if (temp == 'G')
            leftG++;
        else if(temp == 'B')
            minMoveLeft += leftG;
        if (rightTemp == 'G')
            rightG++;
        else if (rightTemp == 'B')
            minMoveRight += rightG;
    }
    minMove = min(minMoveLeft, minMoveRight);
    cout << minMove << endl;
    return 0;
}
O(n)时间复杂度的方法。调整的目标是将所有女孩放到队列前方或者队列后方，男孩和女孩之间只有一处挨着的地方，
男孩和男孩之间，女孩和女孩之间不用排序。思路是计算把女孩都放在队列前部和都放在队列后部分别所需要交换次数
两者的最小值即为所求的答案。

观察一个随机的队列中，考虑把G放在队列前方所需要的移动次数：如BGB当一个G前有一个B，可以把G前面的B移动一次，成GBB。
BGGB需要移动两次，而BBGGB，需要移动4次，虽然不是最优解（G前有两个B，一共有2G），记下这种方法所需要的最少移动次数。

再来考虑把G放在队列后方所需要的移动次数：还是BBGGB，只需要2次移动（G后面有一个B，一共两个G），
记下这种方法所需要的最少移动次数。

将两者的结果取最小值。

发表于 2017-04-01 10:27:40 回复(2)
JacobGo！头像 JacobGo！
最优的情况肯定是，男孩全部在左边，或者男孩全部在右边。
两种情况都计算一下，去最小值即可 
package go.jacob.day913;

import java.util.ArrayList;
import java.util.Scanner;

public class Demo2 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String str=sc.next();
		int len=str.length();
		ArrayList<Integer> boys=new ArrayList<Integer>();
		ArrayList<Integer> girls=new ArrayList<Integer>();
		for(int i=0;i<len;i++){
			if(str.charAt(i)=='B')
				boys.add(i);
			else
				girls.add(i);
		}
		int timeB=0,timeG=0,index=0;
		for(int i=0;i<boys.size();i++){
			timeB+=boys.get(i)-index;
			index++;
		}
		index=0;
		for(int i=0;i<girls.size();i++){
			timeG+=girls.get(i)-index;
			index++;
		}
		System.out.println(Math.min(timeB, timeG));
		sc.close();
	}
}


发表于 2017-09-13 10:13:44 回复(0)
☠头像 ☠
### 分析
事实上，最终的结果只有两种可能，要么是GGG...BBB，要么是BBB...GGG。我们不妨考虑B，我们可以事先求出B全部在左边和全部在右边两种情况下的和。然后对当前每个B的下标求和，显然我们每进行一次有用的调整必然使当前的和+1或者-1。那么，我们只要计算出当前的和与最终结果的和的差就行了，由于最终结果有两种情况，我们取最小值即可。

### 我的答案
```cpp
#include<iostream>
#include<string>
using namespace std;
int main(){
    string s;
    cin>>s;
    int cntB=0;
    int valB=0;
    for(int i=0;i<s.length();i++){
        cntB+=s[i]=='B';
        valB+=s[i]=='B'?i:0;
    }
    int leftB=valB-cntB*(cntB-1)/2;
    int rightB=(2*s.length()-cntB-1)*cntB/2-valB;
    cout<<min(leftB,rightB)<<endl;
}
```
发表于 2017-03-31 13:09:19 回复(0)
别理我头像 别理我
#coding = utf-8
import sys

if __name__ == "__main__":
    # 读取第一行的n
    a = sys.stdin.readline().strip()
    # a = "GGBBBB "
    B_num = 0
    for i in a:
        if i == 'B':
            B_num += 1
    G_num = len(a) - B_num
    if G_num == 0 or B_num == len(a):
        print 0
    else:
        # print B_num, G_num
        # 左男右女
        left_B_num = 0
        left_G_index = []
        right_B_index = []
        for i in range(B_num):
            if a[i] == 'B':
                left_B_num += 1
            else:
                left_G_index.append(i)
        for i in range(B_num, len(a)):
            if a[i] == 'B':
                right_B_index.append(i)

        result_B = 0
        for i in range(len(left_G_index)):
            result_B += right_B_index[i] - left_G_index[i]

        # 左女右男
        left_G_num = 0
        left_B_index = []
        right_G_index = []
        for i in range(G_num):
            if a[i] == 'G':
                left_G_num += 1
            else:
                left_B_index.append(i)
        for i in range(G_num, len(a)):
            if a[i] == 'G':
                right_G_index.append(i)

        # print left_B_index
        # print right_G_index
        result_G = 0
        for i in range(len(left_B_index)):
            result_G += right_G_index[i] - left_B_index[i]

        print min(result_B, result_G)

发表于 2017-03-25 22:42:26 回复(0)
为啥要起名字头像 为啥要起名字
import sys
s=sys.stdin.readline().strip()
countB=(s.count('B')-1)*s.count('B')/2
countG=(s.count('G')-1)*s.count('G')/2
indexB,indexG=0,0
for i in range(len(s)):
    if s[i]=='B':
        indexB+=i
    else:
        indexG+=i
sumB=indexB-countB
sumG=indexG-countG
print(min(sumB,sumG))
发表于 2018-05-17 09:34:57 回复(0)
C/C++
NarcissusAbyss头像 NarcissusAbyss 
/*
因为移动B或者移动G都是等价的，所以我们可以只移动B或者G。
若我们移动B的话，从头开始数，如果B的前面有Vk个G，代表我
们要往前移动Vk下B；同理从尾开始数，如果B的后面有Vs个G，
那么我们也要往后移动Vs下B，所以就是用L把每个B前面有几个G
的个数给累加起来，R把每个B后面有几个G的个数累加起来，然后
再比较一下L和R的大小即可。
*/
int fuk(string s) {
    int len = s.length(), L = 0, R = 0;
    char c = (s[0] == 'G') ? 'B' : 'G';
    int l = 1, r = (s[len - 1] == c) ? 0 : 1;
    for(int i = 1; i < len; i ++) {
        if(s[i] == c) L += l;
        else l ++;
    }
    for(int i = len - 2; i >= 0; i --) {
        if(s[i] == c) R += r;
        else r ++;
    }
    return min(L, R);
}

编辑于 2018-03-21 13:49:32 回复(0)
Java
卖萌の哈士奇头像 卖萌の哈士奇 
//将男生全部移到左边,或者将女生全部移到左边,取两者最小值 import java.util.Scanner;  /**  * Created by meichen on 17-9-7.  */ public class Main { public static void main(String[] args){
        Scanner in = new Scanner(System.in);  while (in.hasNext()){
            String str = in.nextLine();  int gl = 0;  int index = 0;  for(int i = 0;i < str.length(); i++){ if(str.charAt(i) == 'G'){
                    gl += i - index;  index++;  }
            }
            index = 0;  int bl = 0;  for(int i = 0;i < str.length(); i++){ if(str.charAt(i) == 'B'){
                    bl += i - index;  index++;  }
            }
            System.out.println(gl < bl ? gl : bl);  }
    }
}

发表于 2017-09-07 18:34:29 回复(0)
dengziqiang头像 dengziqiang
实际上是求逆序数，可采用归并排序，也可直接双重循环。本答案采用双重循环直接求。
编辑于 2017-03-29 22:50:42 回复(0)
C/C++
轻舞飞扬wst头像 轻舞飞扬wst 

#include<iostream>
#include<string.h>
using namespace std;

int compare(char a[50],int num)
{
	int gleft=0;
	for(int i=0;i<num;i++)
	{
		for(int j=0;j<num-i-1;j++)
		{
			if(int(a[j])==66)
		    {
				char o;
				if(int(a[j+1]==71))
			    {
				    o=a[j];
				    a[j]=a[j+1];
				    a[j+1]=o;
				    gleft++;
			    }
			}
		}
	}
	return gleft;
}

int main()
{
	int p;
	char child[50],childcopy[50];
	cin>>child;
	p=strlen(child);
	for(int i=0;i<p;i++)
		childcopy[p-i-1]=child[i];
	int x,y;
	x=compare(child,p);
	y=compare(childcopy,p);
	if(x<=y)	
	    cout<<x<<endl;
	else
		cout<<y<<endl;
}

编辑于 2017-03-25 21:44:27 回复(0)
Java
YiBuLZ头像 YiBuLZ 
import java.util.ArrayList;
import java.util.Scanner;

/**
 * 调整队形最终的结果为要么男生在左，女生在右，要么反过来
 * 只要BBBBGGGGG 或者GGGGGBBBBB即可
 * 然而，对于初始状态,比如GGBBG,该如何调整呢？
 * 既然最终结果只有两种可能，GGGBB 和BBGGG
 * 那么只要比较这两种可能所付出的代价即可，
 * 那么这么想，既然GGGBB和BBGGG都有可能，是不是，调整的时候只动
 * B或者只动G就行了，因为他们无疑是等价的嘛
 *
 * 好，那么我们就只移动B,用一个list记录每个B所在的位置，
 * 比如GGBBG,list中有个值，2和3，大小为2
 *
 * 好，那么现在关键的问题，就是如何比较了
 * 比如，GGBBG怎么调整，代价最小，最终结果是GGGBB还是BBGGG
 *

 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        sc.close();
        int n = s.length();
        if (n <= 0 || n > 50) {
            throw new RuntimeException("the length is too long");
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i ++) {
            if (s.charAt(i) == 'B') {
                list.add(i);
            }
        }
        int bSize = list.size();
        int indexSum = 0;
        for (int val : list) {
            indexSum += val;
        }
        int left = indexSum - bSize * (bSize - 1) / 2;
        int right = bSize * (n - 1) - indexSum - bSize * (bSize - 1) / 2;
        System.out.println(Math.min(left, right));
    }
}

发表于 2017-04-09 10:28:50 回复(0)
安迪小黑头像 安迪小黑
很简洁的代码，思路大同小异，以boy为例，最终期望的下标和（左边或右边两种情况）与原始下标和作差，取两者中的较小值作为结果即可，代码如下： 
#include <iostream>
#include <cmath>
using namespace std;
int main(){
    string s = "";
    cin >> s;
    int n = s.size();
    int boy = 0, sum = 0, girl;
    for(int i = 0; i < n; i++){
       if(s[i] == 'B'){
           boy++;
           sum += i;
       }
    }
    girl = n - boy;
    cout << min(sum - boy*(boy-1)/2, n*(n-1)/2 - girl*(girl-1)/2 - sum) << endl;
    return 0;
}


发表于 2020-06-19 23:33:25 回复(0)
Gx丶头像 Gx丶 
考虑 男孩+女孩  与女孩+男孩 两种情况即可。最终取最小值。两个for循环基本一致
#include<bits/stdc++.h>
using namespace std;

int main()
{
    string str;
    cin>>str;
    int res;
    int cnt1 = 0;
    int left = -1;
    for(int i =0;i<str.length();i++)//G+B情况
    {
        if(str[i]=='G')
        {
            left++;
            cnt1 = cnt1 + i-left;
        }
    }
    int cnt2 = 0;
    left = -1;
    for(int i =0;i<str.length();i++)//B+G情况
    {
        if(str[i]=='B')
        {
            left++;
            cnt2 = cnt2 + i-left;
        }
    }
    res = min(cnt1,cnt2);
    cout<<res<<endl;
}
发表于 2018-04-15 15:21:22 回复(0)
逗比请来的猴子头像 逗比请来的猴子 

import java.util.Scanner;

/*
 * 此题显然G和B分别站在一起，然后针对两种情况进行讨论：
 * 1.左全是G，右全是B；
 * 1.左全是B，右全是G；
 *
 * 然后求解最小值
 * */
public class BGPalindrome {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String line = scanner.nextLine();

            int min1 = 0;
            int min2 = 0;
            int index1 = 0;
            int index2 = 0;
//            简单的调整位置即可
            for (int i = 0; i < line.length(); i++) {
                char c = line.charAt(i);
                if (c == 'G') {
                    min1 += i - index1++;
                }
                if (c == 'B') {
                    min2 += i - index2++;
                }
            }
            System.out.println(Math.min(min1, min2));
        }
    }
}
发表于 2018-04-11 20:33:29 回复(0)
Python
海阔天空126头像 海阔天空126 
#感谢 @于晨晨  非常清楚的解析

s = input()

G,B,sumG,sumB = 0,0,0,0



for i in range(len(s)):

    if s[i] == "G":

        G += 1

        sumG += i

    else:

        B +=1

        sumB += i

res1 = int(sumG - G*(G-1)/2)

res2 = int(sumB - B*(B-1)/2)

print (min(res1,res2))

发表于 2018-03-26 10:02:46 回复(0)
Java
201803102043497头像 201803102043497

最终结果就是“GGG....GB...BBB"和"BBB....BG...GGGG"两种，如果是第一种的话，只要判定字符串里面是不是包含"BG"这样的字符，如果包含则用"GB”替换第一个“BG”，次数加一，直到字符串中不包含"BG"。如果是第二种的话，只要判定字符串里面是不是包含"GB”这样的字符，如果包含则用"BG"替换第一个“GB"，次数加一,直到字符串中不包含"GB"。输出两种情况次数较小者。 



import java.util.Scanner;  public class 调整队形 { public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);  String line = scanner.nextLine();  String temp = line;  int timeGb = 0;  while (true) { if (temp.contains("BG")) {
                temp = temp.replaceFirst("BG", "GB");  timeGb++;  } else { break ;  }
        } int timeBG = 0;  temp = line;  while (true) { if (temp.contains("GB")) {
                temp = temp.replaceFirst("GB", "BG");  timeBG++;  } else { break;  }
        }
        System.out.println(Math.min(timeBG, timeGb));  }
}


编辑于 2018-03-13 14:56:55 回复(0)
lqqqdu头像 lqqqdu 
//抄的高票答案

import java.util.Arrays;
import java.util.Scanner;

public class Main {

        public static void main(String[] args) {
            // TODO Auto-generated method stub
            //GGBBG
            Scanner scanner = new Scanner(System.in);
            String string = scanner.next();
            int sumB = 0;
            int sumG = 0;
            int countB = 0;
            int countG = 0;
            for(int i = 0;i < string.length();i++){
                if(string.charAt(i) == 'B'){
                    sumB += i;
                    countB++;
                }
                else {
                    sumG += i;
                    countG++;
                }
            }
            int resultB = 0;
            int resultG = 0;
            resultB = sumB - (countB * (countB - 1)) / 2;
            resultG = sumG - (countG * (countG - 1)) / 2;
            if(resultB > resultG){
                System.out.println(resultG);
            }
            else {
                System.out.println(resultB);
            }
        }

    }

发表于 2018-03-01 17:31:28 回复(0)
你和我拥抱不靠近头像 你和我拥抱不靠近
//找出男孩或者女孩数，直接计算就可以。
import java.util.Scanner;

public class Main {
        public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int l =s.length();  //小朋友数
        int count = 0;    //女孩数
        int num = 0;      //女孩位置和
        
        
        for(int i=0;i<l;i++) {
            if(s.charAt(i)=='G') {    
                count++;          
                num += i;
            }
        }
        
        int min = count*(count-1)/2;        //女孩都在左边位置和
        int max = count*(2*l-count-1)/2;    //女孩都在右边的位置和
        
        System.out.println(Math.min((max-num), (num-min)));
    }
}
发表于 2018-01-25 22:51:43 回复(0)
牛客375006号头像 牛客375006号 
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    string str;
    cin>>str;
    int gCount = 0, bCount = 0;     //判断g多还是b多，目的是减少算法运行时间。
    int len = (int)str.size();
    for (int i = 0; i < len; i++) {
        if (str[i] == 'G') {
            gCount++;
        } else {
            bCount++;
        }
    }
    char lessCh = gCount < bCount ? 'G' : 'B';      //哪个字符少，就移动哪个。本质上没区别，仅仅为了优化算法。
    int leftCount = 0, rightCount = 0;      //计算哪边的lessCh多。
    int mid = len / 2;
    for (int i = 0; i < mid; i++) {
        if (str[i] == lessCh) {
            leftCount++;
        }
    }
    int rightBegin = len % 2 == 0 ? mid : mid + 1;
    for (int i = rightBegin; i < len; i++) {
        if (str[i] == lessCh) {
            rightCount++;
        }
    }
    if (leftCount < rightCount) {
        reverse(str.begin(), str.end());
    }
    int moveCount = 0, didMove = 0;
    for (int i = 0; i < len; i++) {
        if (str[i] == lessCh) {
            moveCount += i - didMove;
            didMove++;
        }
    }
    cout<<moveCount;
    return 0;
}
发表于 2017-10-19 18:13:44 回复(0)
提交观点

问题信息

贪心
来自：网易2017春招笔试真...
难度：
52条回答 14059浏览

热门推荐

通过挑战的用户

相关试题

调整队形

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号