首页 > 试题广场 >

鸡鸭分类问题

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


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


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

输入

CCDCC

输出

2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution1_鸡鸭分类问题 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        char[] chars = bf.readLine().toCharArray();
        //分别统计C在前面和D在前面的移动次数
        int retC = 0, retD = 0, count_C = 0, count_D = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == 'C') {
                retC += i - count_C;
                count_C++;//记录出现前面出现多少个 'C',从第i个位置把C移动到底count_c个位置需要移动 i - count_c次
            } else {
                retD += i - count_D;
                count_D++;//记录出现前面出现多少个 'D'
            }
        }
        System.out.println(Math.min(retC,retD));
    }
}
发表于 2019-08-09 20:07:28 回复(1)
要么鸡全在左边,要么鸭全在左边,记录当前顺序变到这两种情况的移动次数,取较小值即可
注:若某鸡的下标为i  其左边还有cnt只鸡  则最少需要i - cnt次才能将其移到左鸡堆的最右边
#include<bits/stdc++.h>
using namespace std;

int solve(string s, char pattern) {
	int res = 0, cnt = 0;;
    for(int i = 0; i < s.length(); i++) {
        if(s[i] == pattern) {
            res += (i - cnt); 
            cnt++;
        }
    }
	return res;
}

int main(){
	string s; 
	while(cin>>s) {
		cout<<min(solve(s, 'C'), solve(s, 'D'))<<endl;
	}   
}
/*
CCDCC
DCCCC
CDCDDD
*/


编辑于 2019-09-01 15:23:34 回复(1)
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)

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)

预处理技巧

很简单,考察每个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)
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)
/*
想法:
像将字符串对半分,分别判断出两边的D的数量,将所有的D往数量多的那个方形移动;
在这个代码AC之后,我发现了一个问题,当左右数量相等时我是默认右移,但是这似乎与两边D的位置有关系,因此不应该简单的右移
估计是本体的数据比较巧合所有能够AC。
*/
import java.util.*;
//import java.lang.*;
public class Main{
    //函数:用于判断字符串中有多少个D
    public static int numofD(String str){
            if(str.length()==0)return 0;
            int count = 0;
            while(str.indexOf('D')!=-1){
                count++;
                str = str.substring(str.indexOf('D')+1);
            }
            return count;
        }
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String str = input.next();
        int len = str.length();
        String leftstr;
        String rightstr;
        int countD = 0;
        //判断长度为奇数的时候,中间的那个字符是否为D
        if(len%2==1){
            if(str.charAt(len%2)=='D')
                countD=1;
        }
        if(len%2==0){
            leftstr = str.substring(0,len%2);
            rightstr = str.substring(len%2);
        }else{
            leftstr = str.substring(0,len%2);
            rightstr = str.substring(len%2+1);
        }
        //判断左移还是右移
        int movecount = 0;
        if(numofD(leftstr)>numofD(rightstr)){//左移
            countD = countD+numofD(leftstr)+numofD(rightstr);
            //开始统计移动次数
            StringBuffer sb = new StringBuffer();
            sb.append(str);
            int j = 0;//目前移动过的D的次数
            for(int i = 0;i<countD;i++){
                movecount = movecount + (sb.indexOf("D") - (j++));
                sb.replace(sb.indexOf("D"),sb.indexOf("D")+1,"C");
            }
        }else{//右移
            countD = countD+numofD(leftstr)+numofD(rightstr);
            //开始统计移动次数
            StringBuffer sb = new StringBuffer();
            sb.append(str);
            int j = 0;//目前移动过的D的次数
            for(int i = 0;i<countD;i++){
                movecount = movecount + (len-1-sb.lastIndexOf("D") - (j++));
                sb.replace(sb.lastIndexOf("D"),sb.lastIndexOf("D")+1,"C");
            }
        }
        
        System.out.println(movecount);
        
    }
}
写复杂了,其实可以按C在左和C在右进行遍历,取最小的移动总数
发表于 2020-04-19 14:15:02 回复(0)
#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s;
    cin >> s;
    string t = s;
    int n = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == 'D')
            n++;
    }
    int sum[2] = { 0 };
    for (int j = 0; j < n; j++)
    {
        for (int i = 1; i < s.size(); i++)
        {
            int temp;
            if (s[i] < s[i - 1])
            {
                temp = s[i];
                s[i] = s[i - 1];
                s[i - 1] = temp;
                sum[0]++;
            }
        }
    }
    for (int j = 0; j < n; j++)
    {
        for (int i = t.size() - 1; i > 0; i--)
        {
            int temp;
            if (t[i] > t[i - 1])
            {
                temp = t[i];
                t[i] = t[i - 1];
                t[i - 1] = temp;
                sum[1]++;
            }
        }
    }
    int max = sum[0] > sum[1] ? sum[1] : sum[0];
    cout << max;
}
发表于 2020-02-06 10:00:56 回复(0)
#include<bits/stdc++.h>
using namespace std;
string str;
//类似冒泡排序
int main() {
	cin >> str;
	auto pos = str.find("D");
	if (pos == string::npos) {
		cout << 0 << endl;
		return 0;
	}

	int ans = 0;
	auto len = str.length();

	for (auto i=0; i != len - pos; ++i) {
		for (auto j=pos; j != len-1; ++j) {
			if (str[j] == 'D' && str[j] != str[j+1]) {
				swap(str[j], str[j+1]);
				++ans;
			}
		} 
	}
	cout << ans << endl;
	return 0;
}

发表于 2019-10-21 22:09:31 回复(1)
using namespace std;
int main() {
    int ans1 = 0;
    int ans2 = 0;
    //左边鸡和鸭的数量
    int chickNum=0;
    int duckNum=0;
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i++) {
//将鸡向左移
        if (str.at(i) == 'C'){
            ans1 += i-chickNum;
            chickNum++;
        }
//将鸭向左移
        else{
            ans2 += i-duckNum;
            duckNum++;
        }
    }
    cout << min(ans1, ans2) << endl;
}
发表于 2019-10-04 04:44:19 回复(0)
import java.util.Scanner;

//鸡鸭调整
/*农场有n只鸡鸭排为一个队伍,鸡用“C”表示,鸭用“D”表示。当鸡鸭挨着时会产生矛盾
 * 。需要对所排的队伍进行调整,使鸡鸭各在一边。每次调整只能让相邻的鸡和鸭交换位置,
 * 现在需要尽快完成队伍调整,你需要计算出最少需要调整多少次可以让上述情况最少。
 * 例如:CCDCC->CCCDC->CCCCD这样就能使之前的两处鸡鸭相邻变为一处鸡鸭相邻,需要调整队形两次。
 */
//40
public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] arr1 = sc.next().toCharArray();
		char[] arr2 = arr1.clone();
		char ji = 'C', ya = 'D' ;
		int k1 = 0;
		int k2 = 0;
		for(int i=0;i<arr1.length;i++){
			if(arr1[i]==ji){
				char temp = arr1[i];
				int j= i-1;//模拟插入排序
				while(j>=0 && arr1[j]==ya){
					arr1[j+1] = arr1[j];
					k1++;
					j--;
				}
				arr1[j+1] = temp;
			}
			
			if(arr2[i]==ya){
				char temp = arr2[i];
				int j= i-1;//模拟插入排序
				while(j>=0 && arr2[j]==ji){
					arr2[j+1] = arr2[j];
					k2++;
					j--;
				}
				arr2[j+1] = temp;
			}
		}
		System.out.println(Math.min(k1, k2));
		
	}
}

发表于 2019-09-14 09:25:35 回复(0)
其实就是两种情况,把C往左边赶 或 把D往左边赶;遇到左边不是C的就找右边最近的C把它交换过去,所需路程就是交换的下边之差,直到没有C为止;两种情况取最小值

#include <iostream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<math.h>
//#include<

using namespace std;

int main()
{
    string str,ori_str;
    cin>>str;
    ori_str = str;
    int counter = 0;
    for(int i = 0;i<str.size();i++)
    {
        if(str[i] != 'C')
        {
            int index = -1;
            for(int j = i+1;j<str.size();j++)
            {
                if(str[j] == 'C')
                    index = j;
            }

            if(index != -1)
            {
                counter += index-i;
                swap(str[i],str[index]);
            }else {
                break;
            }
        }
    }

    int counter2 = 0;
    str = ori_str;
    for(int i = 0;i<str.size();i++)
    {
        if(str[i] != 'D')
        {
            int index = -1;
            for(int j = i+1;j<str.size();j++)
            {
                if(str[j] == 'D')
                    index = j;
            }

            if(index != -1)
            {
                counter2 += index-i;
                swap(str[i],str[index]);
            }else {
                break;
            }
        }
    }

    cout<<min(counter,counter2)<<endl;

    return 0;
}


发表于 2019-08-23 17:05:10 回复(0)
其实这就是一个 “只有两种字母元素”的冒泡排序问题,一个字符串需要按照字符从小到大或者从大到小排列【利用'C'<'D'】
#include <iostream>
using namespace std;
int solve(string cd)
{
   int len=cd.length();
    char tmp;
    int sw=0;
   for (int i=0;i<len-1;i++){
       for (int j=0;j<len-i-1;j++)
       {       
           if(cd[j]>cd[j+1]){
           tmp=cd[j];cd[j]=cd[j+1];cd[j+1]=tmp;
           sw=sw+1;
       }
       else continue;
       }
   }
    return sw;
   
}
int main(){
    
    string cd;
    cin>>cd;
    cout<<solve(cd);
    return 0;
}
发表于 2019-08-16 14:31:07 回复(1)
s = input()
#最少的交换次数,让C和D各分在一边
n = len(s)
num_c = 0
num_d = 0
for i in range(n):
    if s[i] == "C":
        num_c += 1
    else:
        num_d += 1
#记录个数较少的字符
num = "C"
if num_c > num_d:
    num = "D"
#记录较小的字符所在的位置
index = []
for i in range(n):
    if s[i] == num:
        index.append(i)
#将个数较少的字符放到左边和右边的交换次数
#取小的那一个
num_left = 0
for i in range(len(index)):
    num_left += index[i] - i
num_right = 0
for i in range(len(index)-1,-1,-1):
    num_right += n-1-(len(index)-1-i) - index[i]
print(min(num_left,num_right))
发表于 2019-08-13 12:06:11 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    while(cin>>s){
        vector<int> v;
        int l = s.length(), cnt=0;
        for(int i=0;i<l;i++){
            if(s[i]=='C')
                v.push_back(i);
        }
        for(int i=0;i<v.size();i++){
            cnt += v[i]-i;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

发表于 2019-07-09 22:13:55 回复(1)
#include<iostream>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int n=0,num=0,count=0,i=0,rev=0;
    for(;i<s.size();i++)
    {
        if(s[i]=='D')
        {
            num=num+i-count;
            ++count;
        }
    }
    n = i-1;
    count = n;
    while(i>=0)
    {
        if(s[i]=='D')
        {
            rev=rev+count-i;
            --count;
        }
        --i;
    }
    num = (num<rev)? num : rev;
    cout<<num<<endl;
    return 0;
}

发表于 2019-07-02 15:34:08 回复(0)
#include<iostream>
#include<string>
using namespace std;
int swap(string &str,int n)
{
    if (n<=1) return 0;
    const char*ch = str.c_str();
    int count = 0; int countC = 0; int countD = 0;
    for (int i = 0; i<n; i++)
    {
       /* if (ch[i] != 'C' || ch[i] != 'D')
        {
            //cout << "error" << endl;
            break;
        }*/
        if (ch[i] == 'C') countC++;
        if (ch[i] == 'D') countD++;
    }
    int j = 0;int k = 0; int h = countC;
    while (ch[j] != '\0'){
         char *ch1;
        ch1 = (char *)malloc(sizeof(char)* n);
        if (ch[j] == 'C')
        {
            ch1[k] = ch[j];
            if (k != j) count+=j-k;
            k++;
        }
        else {
            ch1[h] = ch[j]; h++;
        }
        j++;
    }
    return count;
}
int main()
{
    string str;
    cin >> str;
    int n=str.length();
    cout<< swap(str, n);
    //system("pause");
    return 0;
}
发表于 2019-04-09 17:00:33 回复(0)
思路:要么把鸡都放到左边,要么把鸡都放到右边,在确定其中一种可能性后,选择移动鸡还是鸭不影响结论。
对于假定的一种情况例如把鸡都放到左边,那么所移动的次数可以用其初始坐标和减去末态坐标和来得到。
基于该思路,代码如下:
#include<stdio.h>
#include<string>
usingnamespacestd;
 
classSolution {
    public:
    int solve(char str[], int length) {
        // 末态需要先统计C的数量再运用sum公式计算,初态则不必
        int count = 0,count_left = 0, count_right = 0;
        for(int i=0; i<length; i++) {
            if(str[i]=='C') {
                count++,count_left += i+1, count_right += length-i-1;
            }
        }
        count = count*(count+1)/2;
        returncount_left <= count_right ? count_left - count : count_right - count;
    }
};
 
intmain(void) {
    charinput[100];
    scanf("%s", &input);
    int l=0;
   while(input[i]!='\0') l++;l++;
    intresult = Solution().solve(input, l);
    printf("%d", result);
}

发表于 2018-11-25 19:08:01 回复(0)
看了一下讨论区的,好多都是没有判断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)
"""
分两种情况,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)