首页 > 试题广场 >

鸡鸭分类问题

[编程题]鸡鸭分类问题

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

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

输入描述:

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

输出描述:

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

示例1

输入

CCDCC

输出

算法知识视频讲解

Python

牛客79242770号

s=input()

count=0
sumC=0
sumD=0
for i in range(len(s)):
    if s[i]=='C':
        sumC+=i-count
        count+=1
count=0
for i in range(len(s)):
    if s[i]=='D':
        sumD+=i-count
        count+=1
print(min(sumC,sumD))

发表于 2020-03-24 12:47:09 回复(0)

Python

我要扛offer回家

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))

编辑于 2019-09-14 11:35:06 回复(0)

Python

frank_123

把C或者 D全部移动到一边就可以了，计算次数

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]))

发表于 2019-09-13 17:02:38 回复(0)

Python

贾志统

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_)

发表于 2019-08-22 23:04:05 回复(0)

Python

欧巴禾

def f(s): if not s: return 0  else:
        count=0  for i in range(len(s)): if s[i]=='C':
                count+=1  return count
all = input()
n = len(all)
total = 0 for i in range(n-1): if all[i]=='D':
        select = all[i+1:]
        total+=f(select) print(total)

发表于 2019-08-13 11:34:35 回复(0)

Python

ElonB

"""
分两种情况，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)

编辑于 2019-07-10 16:15:53 回复(1)