农场有n只鸡鸭排为一个队伍,鸡用“C”表示,鸭用“D”表示。当鸡鸭挨着时会产生矛盾。需要对所排的队伍进行调整,使鸡鸭各在一边。每次调整只能让相邻的鸡和鸭交换位置,现在需要尽快完成队伍调整,你需要计算出最少需要调整多少次可以让上述情况最少。例如:CCDCC->CCCDC->CCCCD这样就能使之前的两处鸡鸭相邻变为一处鸡鸭相邻,需要调整队形两次。
输入一个长度为N,且只包含C和D的非空字符串。
使得最后仅有一对鸡鸭相邻,最少的交换次数
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)); } }
#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 */
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.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; } }
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)); } }
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); } }
/* 想法: 像将字符串对半分,分别判断出两边的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在右进行遍历,取最小的移动总数
#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 <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; }
#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);}
""" 分两种情况,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)