小葱有一面由n块砖排成一行形成的墙,砖块有黑白两种颜色。 小葱心目中的墙是黑白两种砖块交替构成的,于是她要把现在的墙进行改造。 每一次修改可以把任意一块砖块的颜色反转(即白变黑或黑变白),请你帮小葱算算至少需要多少次修改才能把现在的墙修改为小葱心目中的墙。
时间: 2023-05-27 10:07:33 浏览: 84
思路:分别计算把当前墙变成以黑色为开头和以白色为开头需要的修改次数,取两者的最小值即可。
具体实现:
1. 以黑色为开头的修改次数:分别计算奇数位置和偶数位置上的不同颜色砖块数量,取两者之和即为需要修改的次数。
2. 以白色为开头的修改次数:同上,只是计算顺序相反。
3. 取两者的最小值。
代码如下:
def min_step(n, bricks):
odd_black = 0 # 奇数位置上黑色砖块数量
even_black = 0 # 偶数位置上黑色砖块数量
odd_white = 0 # 奇数位置上白色砖块数量
even_white = 0 # 偶数位置上白色砖块数量
for i in range(n):
if i % 2 == 0: # 偶数位置
if bricks[i] == 'B':
even_black += 1
else:
even_white += 1
else: # 奇数位置
if bricks[i] == 'B':
odd_black += 1
else:
odd_white += 1
# 以黑色为开头的修改次数
step1 = odd_white + even_black
# 以白色为开头的修改次数
step2 = odd_black + even_white
return min(step1, step2)
n = int(input())
bricks = input().strip()
print(min_step(n, bricks))