鸡鸭分类问题

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

预处理技巧

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

复杂度分析

/*
想法：
像将字符串对半分，分别判断出两边的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);
        
    }
}

#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;
}

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;
}

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

#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;
}

#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;
}

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



	}

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

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