首页 > 试题广场 >

多多的字符变换

[编程题]多多的字符变换
  • 热度指数：6934 时间限制：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
算法知识视频讲解
开通博客
头像 醉亦醒时醒亦醉
发表于 2024-03-13 19:18:44
这个题目我一开始想复杂了，我想着计算两个字符串出现的字符个数，然后对个数作差，这其实是错误的解，因为自己和自己是无法相消的。 仔细再看了下题目，原来只要对字符排个序就行了，因为从下到达排序，对应位置相减，就一定可以得到最小的差和。至于怎么证明的，我这里简单说一下： #include <ios 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 君莫笑swl
发表于 2021-09-29 15:57:54
多多的字符变换 #include <stdio.h> int cmp(char *a, char *b){ return (int)*a-(int)*b; } int main(){ int len = 0,max=0,min=0; long long res 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 拼多多集团-PDD 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
24条回答 8888浏览

热门推荐

通过挑战的用户

相关试题

多多的字符变换

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号