题解P2133 天作之和
syr1125
·
·
题解
-0x3f 闲话
蒟蒻的第一篇题解~
0x00 简要题意
这道题非常的扯淡哈，第一次看非常的蒙，这里就给一下简化题意。
给你一个字符串 A 每次操作可以交换 A 串里相邻的两个数字，看多少次操作能把他变成 S 串，输出第二小的操作次数。
0x01分析
首先，我们解决这个第二小，可以发现，在操作次数大于 2 时，第一小和第二小没有区别。否则，第二小会比第一小多两次操作。
可以发现这就是一个求逆序对的题啊。
0x02 实现
首先，我们把 A 串中每一个数字在什么位置记录在 vis 数组里。
然后。就是根据 vis 数组记录 S 串的每一个数字应该在相对于 A 数组的位置。
有点绕，我们拿样例解释一下。
$S$ : ```1 2 3 4 5 6```
$vis$ : ```1 2 3 6 5 4```
操作后的 $S$ : ```1 2 3 6 5 4```
然后计算操作后的 $S$ 中逆序对的数量就行了。
逆序对，就用 $O(n^2)$ 的暴力算法吧。
## 0x03 代码
期待已久的代码环节！
```
//by syr1125
//luogu 题解
#include <bits/stdc++.h>
using namespace std;
string a, b;
int vis[10];
int main()
{
cin >> a >> b;
for (int i = 0; i < a.size(); i ++)
{
vis[a[i] - '0'] = i + 1;
}
for (int i = 0; i < b.size(); i ++)
{
b[i] = vis[b[i] - '0'];
}
//存储
int cnt = 0;
for (int i = 0; i < b.size(); i ++)
{
for (int j = i + 1; j < b.size(); j ++)
{
if (b[j] < b[i]) cnt ++;
}
}
//计算逆序对
//快乐的输出
if (cnt <= 2) cout << cnt + 2 << endl;
else cout << cnt << endl;
return 0; //好习惯
}
```
###### ~~管理员大大通过吧。~~