【2019校招真题】鸡鸭分类问题（python）

题目描述：

农场有n只鸡鸭排为一个队伍，鸡用“C”表示，鸭用“D”表示。当鸡鸭挨着时会产生矛盾。需要对所排的队伍进行调整，使鸡鸭各在一边。每次调整只能让相邻的鸡和鸭交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如：CCDCC->CCCDC->CCCCD这样就能使之前的两处鸡鸭相邻变为一处鸡鸭相邻，需要调整队形两次。

输入描述:

输入一个长度为N，且只包含C和D的非空字符串。

输出描述:

使得最后仅有一对鸡鸭相邻，最少的交换次数

示例1

输入

CCDCC

输出

2

解题思路：

交换次数最少，存在两种情况：

（1）把'C'全部交换到左边；

（2）把'D'全部交换到左边；

取两者的较小值即可。

完整代码：

import sys
s = sys.stdin.readline().strip()
res_c = 0
res_d = 0
l = 0
r = 0
for i in range(len(s)):
  if s[i] == 'C':
    res_c += i - l
    l += 1
  if s[i] == 'D':
    res_d += i - r
    r += 1
print(min(res_c, res_d))