题解：P2133 天作之合

· · 题解

题目描述：

P2133 题目传送门

这里应该是本题截止到这篇文章发布前唯一的逆序对正解。

题意简化

给你一个字符串 A 每次操作可以交换 A 串里相邻的两个数字，看多少次操作能把他变成 S 串，输出第二小的操作次数。(转载自这里)

题目思路

  1. 可以发现，直接求 A 与 S 的逆序对个数，也就是需要交换的数字的对数，就能求出最优解，但我们要的是次优解，于是进行分析：

  2. 思考能得到：次优解只会在最优解与最优解加 2 中产生，因为如果有多个最优解，则次优解就是最优解；如果只有一个最优解，则可以把任意两个相邻数交换再换回，就产生了次优解，也就是最优解加 2。

  3. 观察两组数据：

data1：

123456
234156

data2：

123456
132465

在第一组数据中，其实可以看成只有 1 一个数的位置在与其他数交换，所以最优解当然只有一个。

而在第二组数据中却有多个数的位置在与其他数交换。（可以看成 2 和 5 在移动）所以问题转化成了处理关于 2 的位置变化的子问题和关于 5 的位置变化的子问题这样的多个子问题，最优解便有多个。

  1. 总结一下，当这个数据只能看成多个子问题时，最优解就会有多个。（因为 data1 也能看成 2，3，4 三个数在移动）或者说，当一个数据能看成一个子问题时，次优解才不等于最优解。

所以，只当碰到这样的序列时：

1,2,3,...i+1,i+2,i+3,...i+k,i,i+k+1,i+k+2,...n-1,n

次优解才等于最优解加 2。

  1. 考虑实现：将 data[i] 设为 S 中第 i 个位置的数本来应该在的位置，m[a[i]] 设为 A 中第 i 个位置的数本来应该在的位置，当 data[i]-m[a[i]] 等于逆序对的个数时（最优解），说明 S 中第 i 个位置的数向前或后连续交换最优解次就能得到 A 序列。当存在这种数时，就是次优解不等于最优解的情况。

基本思路到这里就结束了，下面是实现部分。

AC 代码

AC 记录

#include<bits/stdc++.h>
using namespace std;
string a,b;
int data[10];
map<char,int> m; 
int main()
{
    cin>>a>>b;
    a=' '+a;//加上空格，个人习惯使用s[1]~s[6]
    b=' '+b;
    int ans=0,cnt=0;
    for(int i=1;i<=6;i++)m[a[i]]=i;//map标记每个数字正确的位置
    for(int i=1;i<=6;i++)data[i]=m[b[i]];//同上，data[i]为b[i]应该在的位置
    for(int i=1;i<=6;i++)
    for(int j=i+1;j<=6;j++)
    if(data[j]<data[i])ans++;//求逆序对个数
    if(ans<2)ans+=2;//特判，如果没交换或者只交换了一次，必定属于最优解加2的情况
    else
    {
        for(int i=1;i<=6;i++)
        if(abs(data[i]-m[a[i]])==ans)cnt++;//特殊情况出现
        if(cnt==1)ans+=2;//只有一个数在移动
    }
    cout<<ans;
    return 0;
}

总结

很好的思维题，这让我的代码旋转。