首页 > 试题广场 >

红和绿

[编程题]红和绿

热度指数：483 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。牛牛现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将会被覆盖。牛牛的目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。牛牛想知道他最少需要涂染几个正方形。
如样例所示: s = RGRGR
我们涂染之后变成RRRGG满足要求了,涂染的个数为2,没有比这个更好的涂染方案。

输入描述:

输入包括一个字符串s,字符串s长度length(1 ≤ length ≤ 50),其中只包括'R'或者'G',分别表示红色和绿色。

输出描述:

输出一个整数,表示牛牛最少需要涂染的正方形数量

示例1

输入

RGRGR

输出

算法知识视频讲解

Python

专苎

str=input()
n=len(str)
maxcount=-1
for x in range(n):
count=0
for i in range(x):
if str[i]=='G':
count=count+1
for j in range(x,n):
if str[j]=='R':
count=count+1
if count<maxcount or maxcount==-1:
maxcount=count

print(maxcount)

借鉴了下面python2的答案，修改成python3并成功

将字符串分割成两部分，前面全涂为R，后面全涂为G，前面涂成R的次数加上后面涂成G的次数即为需要涂的总次数，列出每种分隔方法的涂的总次数，最小的那个即是答案。

发表于 2018-09-09 09:41:44 回复(0)