多多君最近在研究字符串之间的变换,可以对字符串进行若干次变换操作:
- 交换任意两个相邻的字符,代价为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;
} 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)
}
} 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.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);
}
}
#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;
} 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 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.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();in.nextLine();
String x = in.nextLine() , y = in.nextLine();
int[] cntd = new int[26] ;
for (int i =0;i<n;i++) {
cntd[x.charAt(i) - 'a'] ++;
cntd[y.charAt(i) - 'a'] --;
}
Deque<Integer> stk = new ArrayDeque<>();
int res = 0,top,ptop;
for (int i =0;i<26;i++){
if (cntd[i] == 0) continue;
ptop = i;
while (!stk.isEmpty() && cntd[stk.peekLast()] * cntd[ptop] < 0) {
top = stk.pollLast();
if (cntd[top]*cntd[top] > cntd[ptop]*cntd[ptop]) {
res+= Math.abs(cntd[ptop] * (top - ptop));
cntd[top]+=cntd[ptop];
cntd[ptop] = 0;
ptop = top;
}
else{
res+= Math.abs(cntd[top] * (top - ptop));
cntd[ptop]+=cntd[top];
cntd[top] = 0;
}
}
if (cntd[ptop] != 0) stk.offerLast(ptop);
}
System.out.print(res);
}
} 可以不用排序,改变顺序不消耗代价,所以问题等价于把两个26维度计数向量cntx,cnty变为一样的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 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);
}
}