农场有n只鸡鸭排为一个队伍,鸡用“C”表示,鸭用“D”表示。当鸡鸭挨着时会产生矛盾。需要对所排的队伍进行调整,使鸡鸭各在一边。每次调整只能让相邻的鸡和鸭交换位置,现在需要尽快完成队伍调整,你需要计算出最少需要调整多少次可以让上述情况最少。例如:CCDCC->CCCDC->CCCCD这样就能使之前的两处鸡鸭相邻变为一处鸡鸭相邻,需要调整队形两次。
输入一个长度为N,且只包含C和D的非空字符串。
使得最后仅有一对鸡鸭相邻,最少的交换次数
CCDCC
2
import sys s=sys.stdin.readline().strip() idx=[] cur_idx=s.find('D') idx.append(cur_idx) while cur_idx!=-1: cur_idx=s.find('D',cur_idx+1) idx.append(cur_idx) idx.remove(-1) lres,rres=0,0 for i,j in zip(range(len(idx)),idx): lres=lres+j-i for i,j in zip(idx[::-1],list(range(len(s)-1,len(s)-len(idx)-1,-1))): rres=rres+j-i print(min(lres,rres))
import sys paras = [] for i in sys.stdin: paras += i.split() def change(s): length = len(s) num1 = 0 num2 = 0 chance2C = -1 for i in range(length): if s[i] == "C": chance2C += 1 num1 += i - chance2C num2 += length - 1 - chance2C - i return min(num1, num2) print(change(paras[0]))
def swap_num(str_): length = len(str_) initial_sum_d = 0 num_d = 0 for j in range(length): if str_[j] == "D": initial_sum_d += j num_d += 1 if initial_sum_d / num_d <= (length-1) / 2: #res_sum_d = num_d * (num_d - 1) // 2 res_sum_d = num_d * (num_d - 1) >> 1 print(initial_sum_d - res_sum_d) else: #res_sum_d = num_d * (length + length - 1 - num_d) // 2 res_sum_d = num_d * (length + length - 1 - num_d) >> 1 print(res_sum_d - initial_sum_d) str_ = input() swap_num(str_)
""" 分两种情况,C排前D排后,C排后D排前,取最小值 对于C排前D排后,只看C,最小交换次数为,s中为C的下标之和,减去排好序后C的下标之和 例如:CCDDCC,排序后CCCCDD,最小交换次数为 C:4->2,5->3,(0+1+4+5)-(0+1+2+3) = 4 """ import sys if __name__ == "__main__": # sys.stdin = open("input.txt", "r") s = input().strip() a = [i for i in range(len(s)) if s[i] == 'C'] ans = min(sum(a) - ((len(a) - 1 + 0) * len(a)) // 2, ((len(s) - len(a) + len(s) - 1) * len(a)) // 2 - sum(a)) print(ans)