首页 > 试题广场 >

鸡鸭分类问题

[编程题]鸡鸭分类问题
  • 热度指数：9806 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
农场有n只鸡鸭排为一个队伍，鸡用“C”表示，鸭用“D”表示。当鸡鸭挨着时会产生矛盾。需要对所排的队伍进行调整，使鸡鸭各在一边。每次调整只能让相邻的鸡和鸭交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如：CCDCC->CCCDC->CCCCD这样就能使之前的两处鸡鸭相邻变为一处鸡鸭相邻，需要调整队形两次。


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


输出描述:
使得最后仅有一对鸡鸭相邻，最少的交换次数
示例1

输入

CCDCC

输出

2
算法知识视频讲解
添加回答
Java
pein531头像 pein531

预处理技巧

很简单，考察每个D的左边和右边有多少个C就行，通过一次遍历数组的预处理得到这个信息
  1. 如果要把所有的D换到左边，就将所有D左边有多少个C加起来（表示将某个D换到这些C的前面）；
  2. 如果要把所有的D换到右边，就将所有D右边有多少个C加起来（便是将某个D换到这些C的后面）。
最后比较两种策略哪种代价低。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static int minStep = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int costL = 0, costR = 0, n = str.length();
        int[] left = new int[n];      // i的左边有多少个C
        int[] right = new int[n];     // i的右边有多少个C
        for(int i = 1; i < str.length(); i++){
            if(str.charAt(i - 1) == 'C'){
                left[i] = left[i - 1] + 1;
            }else{
                left[i] = left[i - 1];
            }
            if(i >= 2){
                if(str.charAt(n - i + 1) == 'C'){
                    right[n - i] = right[n - i + 1] + 1;
                }else{
                    right[n - i] = right[n - i + 1];
                }
            }
        }
        right[0] = str.charAt(1) == 'C'? right[1] + 1: right[1];
        for(int i = 0; i < n; i++){
            costL += str.charAt(i) == 'D'? left[i]: 0;
            costR += str.charAt(i) == 'D'? right[i]: 0;
        }
        System.out.println(Math.min(costL, costR));
    }
}

复杂度分析

获得预处理信息时间复杂度O(n)，在获得预处理信息之后，计算得到每种策略的时间复杂度也都是O(n)，因此算法整体的时间复杂度为O(n)。预处理信息需要两个长度为n的数组存储，因此额外空间复杂度为O(n)。

发表于 2022-01-19 11:10:42 回复(0)
Java
三个火头像 三个火 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int countC = 0;
        int countD = 0;
        int restC = 0;
        int restD = 0;    //C移到左边，前面有几个D就移动几次
                //相反则一样
        for(int i = 0; i < str.length(); i++){
            if(str.charAt(i) == 'C'){
                countC++;
                restC += countD;
            } else {
                countD ++;
                restD += countC;
            }
        }
        System.out.print(restC<restD? restC:restD);
    }
}
发表于 2020-12-27 11:22:02 回复(0)
Java
LeehomWang头像 LeehomWang 
import java.io.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        char[] c=br.readLine().toCharArray();
        int n=0;
        int sum=0;
        for(int i=c.length-1;i>=0;i--){
            if(c[i]=='C')
                n++;
            else
                sum+=n;//D后面有多少个C就需要移动多少次
        }
        System.out.println(sum);
    }
}


发表于 2020-05-08 17:34:50 回复(0)
Java
LHC0512头像 LHC0512

Java解法 
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        System.out.println(Math.min(move(s,'C'), move(s,'D')));
    }

    static int move(String s, char c){
        int count=0;
        int move=0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i)==c){
                //若某鸡的下标为i  其左边还有count只鸡  则最少需要i - count次才能将其移到左鸡堆的最右边
                move+=i-count;
                count++;
            }
        }
        return move;
    }
}


发表于 2020-03-01 10:57:29 回复(0)
Java
Error201803052104654头像 Error201803052104654
看了一下讨论区的,好多都是没有判断C排在左或排在右的情况,所以补上我的代码
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        sc.close();
        int len = str.length();
        int l=0,r=0;
        int resC=0,resD=0;
        for(int i=0;i<len;i++){
            if(str.charAt(i) == 'C'){
                resC += i-l;
                l++;
            }else{
                resD += i-r;
                r++;
            }
        }
        System.out.println(Math.min(resC,resD));
    }
}
发表于 2019-07-24 20:42:34 回复(1)
Java
buaaStu头像 buaaStu 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String input="";
        int result=0;

        input=scanner.nextLine();
        String[] s=input.split("");
        
        int l=0;
        for(int i=0;i<s.length;i++){
            if(s[i].equals("C")){
                result+=i-l;
                l++;
            }
        }
        
        System.out.println(result);
    }
}

编辑于 2019-01-30 09:36:13 回复(2)
提交观点

问题信息

C++工程师 模拟 字符串 2019 数学 Java工程师 招商银行信用卡中心
上传者：小小
难度：
7条回答 14020浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号