多多君最近在研究字符串之间的变换,可以对字符串进行若干次变换操作:
- 交换任意两个相邻的字符,代价为0。
- 将任意一个字符a修改成字符b,代价为 |a - b|(绝对值)。
现在有两个长度相同的字符串X和Y,多多君想知道,如果要将X和Y变成两个一样的字符串,需要的最少的代价之和是多少。
多多君最近在研究字符串之间的变换,可以对字符串进行若干次变换操作:
共三行,第一行,一个整数N,表示字符串的长度。
(1 <= N <= 2,000)
接下来两行,每行分别是一个字符串,表示字符串X和Y。
(字符串中仅包含小写字母)
共一行,一个整数,表示将X和Y变换成一样的字符串需要的最小的总代价。
4 abca abcd
3
其中一种代价最小的变换方案:
都修改为abcd,那么将第一个字符串X最后一个字符a修改为d,代价为|a - d| = 3。
4 baaa aabb
1
其中一种代价最小的变换方案:
首先将第一个字符串通过交换相邻的字符:baaa -> abaa -> aaba,代价为0。
然后将第二个字符串修改最后一个字符b:|b - a| = 1。
两个字符都修改为aaba,所以最小的总代价为1。
3 abc xyz
69
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; string a, b; cin >> a >> b; sort(a.begin(), a.end()); sort(b.begin(), b.end()); int res = 0; for(int i = 0 ; i < n ; ++ i) { if(a[i] != b[i]) { int mu = abs(b[i] - a[i]); res += mu; } } cout<<res<<endl; return 0; }
n = int(input()) str_one = input() str_two = input() list_1 = [ord(i) for i in str_one] list_2 = [ord(i) for i in str_two] list_1.sort() list_2.sort() ans=0 for i in range(n): ans+=abs(list_1[i]-list_2[i]) print(ans)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); char[] x = br.readLine().trim().toCharArray(); char[] y = br.readLine().trim().toCharArray(); Arrays.sort(x); Arrays.sort(y); int cost = 0; for(int i = 0; i < n; i++) cost += Math.abs(x[i] - y[i]); System.out.println(cost); } }scala版,scala运行得是真慢
import scala.io.StdIn object Main { def main(args: Array[String]): Unit = { val n = StdIn.readInt val x = StdIn.readLine.trim.toCharArray.sorted val y = StdIn.readLine.trim.toCharArray.sorted var cost = 0 for(i <- x.indices) cost += math.abs(x(i).toInt - y(i).toInt) println(cost) } }
#include<iostream> #include<string> #include<algorithm> using namespace std; int getMinSum(string s1, string s2, int n) { if (n <= 0) return 0; /* 1.找到两个字符串中相同的字母, 将s1[i]='|', s2[j]='~'('|'>'z' '~'>'z') 直接删除,还要大量移动元素,增加时间复杂度 m:记录字母的个数 */ int m = n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (s1[i] == s2[j]) { s1[i] = '|'; s2[j] = '~'; m--; break; } } } //2.将两个字符串升序排序 sort(s1.begin(), s1.end()); sort(s2.begin(), s2.end()); //3.统计代价sum=sum+|s1[i]-s2[i]|, 0=<i<=m int sum = 0; for (int i = 0; i < m; i++) { int num = s1[i] - s2[i]; sum += num > 0 ? num : (-num); } return sum; } int main() { int n; cin >> n; string s1, s2; cin >> s1; cin >> s2; int sum = getMinSum(s1, s2, n); cout << sum << endl; system("pause"); return 0; }
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); //这一题理清思路,简单地把字符串排一下序然后就可以直接相互加减了 int N = scanner.nextInt(); String s1 = scanner.next(); String s2 = scanner.next(); char[] chars1 = s1.toCharArray(); char[] chars2 = s2.toCharArray(); Arrays.sort(chars1); Arrays.sort(chars2); int count = 0; for (int i = 0; i < N; i++) { count += Math.abs(chars1[i] - chars2[i]); } System.out.println(count); } }
const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void async function () { // Write your code here var arr=[]; while(line = await readline()){ arr.push(line) } // console.log("arr:",arr) const SeqX = Array.from(arr[1]).sort().join("") // console.log(SeqX); const SeqY = Array.from(arr[2]).sort().join("") // console.log(SeqY); var result=0; for(var i=0;i<arr[0];i++){ result+=Math.abs(SeqX.charCodeAt(i)-SeqY.charCodeAt(i)); } console.log(result) }()
import java.util.Scanner; public class Main { public static void main(String[] args) { int a; Scanner in = new Scanner(System.in); a = in.nextInt(); String str1 = in.next(); String str2 = in.next(); char[] cs1 = str1.toCharArray(); char[] cs2 = str2.toCharArray(); int result = 0; int l1 = 0; int l2 = 0; for (int i = 0; i < a; i++) { l1 += cs1[i]; l2 += cs2[i]; } result = Math.abs(l1 - l2); System.out.println(result); } }
n = int(input()) s1 = input() s2 = input() letter_dict = {} for char in s1: letter_dict[char] = letter_dict.get(char, 0) + 1 for char in s2: letter_dict[char] = letter_dict.get(char, 0) - 1 i = j = 'a' cost = 0 while i <= 'z' and j <= 'z': # i <= 'z' and while i not in letter_dict&nbs***bsp;letter_dict[i] <= 0: i = chr(ord(i) + 1) if i == '{': break while j not in letter_dict&nbs***bsp;letter_dict[j] >= 0: j = chr(ord(j) + 1) if j == '{': break if j <= 'z': cost += abs(ord(i) - ord(j)) letter_dict[i] -= 1 letter_dict[j] += 1 # print(letter_dict) print(cost)
import string n=int(input()) s1=input() s2=input() d1={} d2={} for i in range(n): d1[s1[i]]=d1.get(s1[i],0)+1 d2[s2[i]]=d2.get(s2[i],0)+1 total=0 rest=0 for letter in string.ascii_lowercase: rest+=d1.get(letter,0)-d2.get(letter,0) total+=abs(rest) print(total)
仔细观察题目,交换是不需要代价的,那么排序就行了
import java.util.Arrays; import java.util.Scanner; /** * * @date 2021/8/29 - 20:52 */ public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int N = cin.nextInt(); cin.nextLine(); String str1 = cin.nextLine(); String str2 = cin.nextLine(); char[] chars1 = str1.toCharArray(); char[] chars2 = str2.toCharArray(); Arrays.sort(chars1); Arrays.sort(chars2); int res = 0; for (int i = 0; i < chars1.length; i++) { res += Math.abs((int)(chars1[i]-chars2[i])); } System.out.println(res); } }
package main import ( "fmt" "sort" ) func main(){ n := 0 s1 := "" s2 := "" fmt.Scan(&n) fmt.Scanln(&s1) fmt.Scanln(&s2) fmt.Println(getSum(s1, s2)) } func getSum(s1 string, s2 string) int { arr1 := []int{} for i := 0; i < len(s1); i ++ { arr1 = append(arr1, int(s1[i] - 'a')) } sort.Ints(arr1) arr2 := []int{} for i := 0; i < len(s2); i ++ { arr2 = append(arr2, int(s2[i] - 'a')) } sort.Ints(arr2) sum := 0 for i := 0; i < len(arr1); i ++ { sum += abs(arr1[i], arr2[i]) } return sum } func abs(x int, y int) int { if x > y { return x - y } return y - x }
import java.util.Scanner; import java.util.Arrays; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); in.nextLine(); String a = in.nextLine(); String b = in.nextLine(); char[] chA = a.toCharArray(); char[] chB = b.toCharArray(); Arrays.sort(chA); Arrays.sort(chB); int sum = 0; for (int i = 0; i < n; i++) { sum += Math.abs(chA[i] - chB[i]); } System.out.println(sum); } }
import java.util.Scanner; import java.util.Arrays; public class Main{ public static void main(String[] args){ Scanner input = new Scanner(System.in); int num = input.nextInt(); String str1 = input.next(); String str2 = input.next(); if(num <= 0){ return; } int zdj = 0; if(str1.length() == str2.length() && num == str1.length() ){ char[] ch1 = str1.toCharArray(); char[] ch2 = str2.toCharArray(); if(str1.equals(str2)){ System.out.println(zdj); return; } Arrays.sort(ch1); Arrays.sort(ch2); for(int i=0;i<num;i++){ if(ch1[i] != ch2[i]){ zdj += Math.abs(ch1[i]-ch2[i]); } } } System.out.println(zdj); } }
public class CharChange { public static void main(String[] args) { /** * 因为交换字符没有代价,所以将两个字符串分别排序然后逐位比较计算代价即可 * 为什么升序就不用删除相等元素了??? */ Scanner sc = new Scanner(System.in); int anInt = Integer.parseInt(sc.nextLine()); String line = sc.nextLine(); String otherStr = sc.nextLine(); if (line.equals(otherStr)) { System.out.println("0"); } char[] chars = line.toCharArray(); char[] otherChars = otherStr.toCharArray(); Arrays.sort(chars); Arrays.sort(otherChars); int sum = 0; for (int i=0;i<anInt;i++) { sum+=Math.abs(chars[i]-otherChars[i]); } System.out.println(sum); } }