P7755 [COCI2012-2013#3] POREDAK

· · 题解

题意：先给定 n 个互不相等的字符串，再给定这 n 个字符串的另一种排列顺序，求出第二种排列顺序中，字符串的相对位置和第一种排列方式相等的个数。

什么叫相对位置相等？我们拿样例来做一下示范：

\text {alpha} $ $ \text {beta} $ $ \text {gamma} \text {alpha} $ $ \text {gamma} $ $ \text {beta}

答案是 2 。 因为在第一种排列顺序中， \text {alpha} 的位置在 \text {beta} 前，第二种排列顺序中， \text {alpha} 的位置仍在 \text {beta} 前， 所以答案要加1。这就是相对位置，也就是逆序对。

同理， \text {alpha} 和 \text {gamma} 也是如此，所以答案就是 2 。

所以，只要在两种排列顺序中，有两个字符串的相对位置不变，答案就加1。

这里有两种选择：一种归并排序找逆序对，然后直接计算答案，另一种则是暴力枚举。由于 n \leq 2 5 0 0 ，直接暴力即可。

注意：这里首先要把第二种排列顺序中的字符串所在位置记录下来，建议用 \text {map} 。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define r register
string zyqq[2505];//一开始的排列顺序
map<string,int> b;
int main(){
    int n;
    cin >> n;
    for (register int i=1;i<=n;i++){
        cin >> zyqq[i];
    }
    for (register int i=1;i<=n;i++){
        string zyq;
        cin >> zyq;
        b[zyq]=i;//把字符串的位置记录下来
    }
    int ans=n*(n-1)/2,zyq=0;//ans是题目中已经给出的b的答案
    for (register int i=1;i<=n;i++){
        for (register int j=i+1;j<=n;j++){
            if (b[zyqq[i]]<b[zyqq[j]]) zyq++;//因为j>i,所以第一种顺序中，两个字符串的相对位置已经确定，只需在比较第二种顺序中，这两个字符串的相对位置即可。
        }
    }
    cout << zyq << '/' << ans;
    return 0;
}