P2133题解

zyl0128_alpha · 2024-01-30 15:07:13 · 题解

思路

这个题目其实可以转化一下。它的本质就是求出把 A 变为 S 后，以每个字符在 A 中的下标按照在 S 中出现的顺序排列，逆序对的个数。所以，可以记录下每一个字符的位置，再找逆序对即可。

代码

#include<bits/stdc++.h>
using namespace std;
string a,s;
map<char,int> mp;
int main(){
    cin>>a>>s;
    int l1,l2,ans=0;
    l1=a.size();
    l2=s.size();
    for(int i=0;i<l1;i++){
        mp[a[i]]=i; 
    }
    for(int i=0;i<l2;i++){
        s[i]=mp[s[i]]; 
    }
    for(int i=0;i<l2;i++){
        for(int j=i+1;j<l2;j++){
            if(s[i]>s[j]){
                ans++;
            }
        }   
    }
    if(ans<=2){
        cout<<ans+2;
    }else{
        cout<<ans;
    }
    return 0;
}