自动搬运

查看原文

来自洛谷，原作者为

	Zhou_yu 这个家伙很懒，但什么都想留下||CZOIer

搬运于2025-08-24 21:34:21，当前版本为作者最后更新于2024-08-05 19:22:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目描述：

P2133 题目传送门

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

题意简化

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

题目思路

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

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

3. 观察两组数据：

data1：

123456
234156

data2：

123456
132465

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

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

4. 总结一下，当这个数据只能看成多个子问题时，最优解就会有多个。（因为 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$。

5. 考虑实现：将 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;
}

总结

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