首页 > 试题广场 >

多多的字符变换

[编程题]多多的字符变换
  • 热度指数:7442 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

多多君最近在研究字符串之间的变换,可以对字符串进行若干次变换操作:

  1. 交换任意两个相邻的字符,代价为0。
  2. 将任意一个字符a修改成字符b,代价为 |a - b|(绝对值)。
现在有两个长度相同的字符串X和Y,多多君想知道,如果要将X和Y变成两个一样的字符串,需要的最少的代价之和是多少。


输入描述:
共三行,第一行,一个整数N,表示字符串的长度。
(1 <= N <= 2,000)
接下来两行,每行分别是一个字符串,表示字符串X和Y。
(字符串中仅包含小写字母)


输出描述:
共一行,一个整数,表示将X和Y变换成一样的字符串需要的最小的总代价。
示例1

输入

4
abca
abcd

输出

3

说明

其中一种代价最小的变换方案:
都修改为abcd,那么将第一个字符串X最后一个字符a修改为d,代价为|a - d| = 3。
示例2

输入

4
baaa
aabb

输出

1

说明

其中一种代价最小的变换方案:
首先将第一个字符串通过交换相邻的字符:baaa -> abaa -> aaba,代价为0。
然后将第二个字符串修改最后一个字符b:|b - a| = 1。
两个字符都修改为aaba,所以最小的总代价为1。
示例3

输入

3
abc
xyz

输出

69
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变为一样的
假设有一种方案将cntx,cnty 变为 cnt,那么一定可以等价对应唯一的 将cntx 变为 cnty的某种方案。
所以考虑cntd = cntx - cnty , 显然cntd向量各位和为0,容易证明尽可能使得交换的区间处于包含关系而不是交叉关系最小,用栈进行处理,当出现可以相消就相消
发表于 2025-06-12 16:36:30 回复(0)