自动搬运

查看原文

来自洛谷，原作者为

	liuxy1234 『既然选择了远方，便只顾风雨兼程』 || 只想静静地被遗忘

搬运于2025-08-24 22:32:48，当前版本为作者最后更新于2022-01-28 10:34:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

看到这题面，我们就会想起顺序对。

但是用什么来呢？ 归并？

当我们看到数据范围 $n \le 2500$ 时，就不用担心了。

暴力！！！

上代码。

#include <bits/stdc++.h>
#define int  long long
using namespace std;

map <string, int>a;//map真不错。
string s;
int b[10000];
int cnt;
signed main(){
	std::ios::sync_with_stdio(0);
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> s;
		a[s] = i;
	}
	for(int i = 1;i <= n;i++)
	{
		cin >> s;
		b[i] = a[s];
	}
	for(int i = 1;i <= n;i++)
	{
		for(int j = i + 1;j <= n;j++)
		{
			if(b[i] < b[j])cnt++;
		}
	}
	cout << cnt << '/' << (n * n - n) / 2;
	return 0;
}