首页 > 试题广场 >

调整队形

[编程题]调整队形

热度指数：4582 时间限制：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

输出

算法知识视频讲解

Python

海阔天空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)

Python

SrCMpunk

# -*- coding:utf-8 -*-  
if __name__ == '__main__':
    s = raw_input().strip()
    sumlistB = []
    countB = 0  
    sumlistG = []
    countG = 0  
    for i in range(0, len(s)):
    if s[i] == 'B':
        sumlistB.append(countB) 
    else:
        countB += 1  
    if s[i] == 'G':
        sumlistG.append(countG) 
    else:
        countG += 1  
    resultB = sum(sumlistB)
    resultG = sum(sumlistG) 
    print min(resultB,resultG)

发表于 2017-03-27 12:40:41 回复(0)