多多的字符变换【拼夕夕真题】

2.多多的字符变换

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

1. 交换任意两个相邻的字符，代价为0。
2. 将任意一个字符a修改成字符b，代价为 |a - b|（绝对值）。

现在有两个长度相同的字符串X和Y，多多君想知道，如果要将X和Y变成两个一样的字符串，需要的最少的代价之和是多少。

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

共三行，第一行，一个整数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

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main() {
    int n;
    cin>>n;
    string str1, str2;
    cin >> str1;
    cin >> str2;
    map<char,int> mymap;
    for(char c:str2)
        mymap[c] += 1;
    vector<char> str1_reserve;
    for(char c:str1){
        if(mymap.count(c) > 0){
            mymap[c] -- ;
            if(mymap[c] == 0){
                mymap.erase(c);
            }
        }else{
            str1_reserve.push_back(c);
        }
    }
    vector<char> str2reserve;
    for(pair<char,int> p:mymap){
        for(int j=0;j<p.second;j++){
            str2reserve.push_back(p.first);
        }
    }
    int cost = 0;
    sort(str1_reserve.begin(),str1_reserve.end());
    sort(str2reserve.begin(),str2reserve.end());
    for(int i=0;i<str1_reserve.size();i++){
        cost += abs(str1_reserve[i] - str2reserve[i]);
    }
    cout << cost << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")