P2133 天作之合 题解
P2133 天作之合 题解
前言（碎碎念）
不要听信标签，标签标的是搜索，但是事实上用逆序对解这道题更加地巧妙与快捷，本人开始也是绞尽脑汁在想搜索怎么做。
话不多说，正文开始。
题目大意
给定初始字符串 S 与目标字符串 A，每次能调换相邻的两个字母，问最少需要多少次能将 S 变为 A。
这里有几个问题和特别需要注意的点的：
- Q： 适合的字符串不是和 A 相似的吗？为什么这里变成相同了呢？
A： 回到题目中，小明认为合适程度第二小的女生才是适合的伴侣，对于任何一个与目标字符串相似的字符串 H，总能通过一次交换使得 H 变成 A，所以 A 一定是一个符合题意的最终状态。
- Q：为什么 A 和 S 相同时这个思路的答案时错误的？
A：这里就涉及到这个思路的注意事项了。
我们仔细读题不难发现，诶？合适值要包括同桌和理想女生，也就是说，当字符串的变换至少进行两次的前提下，最少会有三个不同的女生出现在一个完整的过程中，也就是说合适值小于
ans=(ans>2?ans:ans+2)那么思路整理完之后就开始构建实现过程了。
代码实现
题目中的 S 和 A 都是长度为
那么我们可以做以下操作：
- 把字符串的每一位分别设为 a 位到 f 位，并且将 S 串中的每一个数字与字母相互对应，比如下面的 S 串：
S=[231465]
2 -> a
3 -> b
1 -> c
4 -> d
6 -> e
5 -> f- 将 A 串的每一个数字用字母替代，如：
就变为：
到这里，题目就变为了如何将处理后的 A 串按照字典序排列，即：
此处用逆序对个数求解。
- 对于每一对
i ，j ，i<j ，若A_{i}>A_{j} ，则为一个逆序对，答案计数加一，最后得到的计数便是第二小的合适值也就是题目输出。AC 代码
#include<bits/stdc++.h>
#define N 11
using namespace std;
int a,s,t,ans;
int pre[N],ed[N];
int main(){
cin>>a>>s;
while(a>0){//a串预处理
t++;
pre[a%10]=7-t;
a/=10;
}
while(s>0){//s串预处理
ed[t]=pre[s%10];
s/=10;
t--;
}
for(int i=1;i<6;i++){
for(int j=i+1;j<=6;j++){
if(ed[i]>ed[j]) ans++;//找逆序对
}
}
cout<<(ans>2?ans:ans+2);//输出+特判
return 0;
}