题解

liuxy1234 · 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;
}