P3531 [POI2012]LIT-Letters（求逆序对）

布满荆棘的人生 2022-12-31 01:26 151阅读 0赞

题目传送门：[https://www.luogu.com.cn/problem/P3531][https_www.luogu.com.cn_problem_P3531]

# 题意 #

给出只包含大写字母的字符串 A 和字符串 B，每次可以交换字符串 A 两个相邻的字符，求 A 变成 B 的最小交换次数。

# 思路 #

这道题给了我一丝熟悉感，就像给定一个数组，我们每次可以交换数组中相邻的两个元素，求将它变成有序需要的最小的交互次数，也就是**求其逆序对个数**。其实它们的运作方式是完全，只不过这里只是将“有序”的基准变成了 “变成 B”。

如果字符串中的字符无法让我们直接完成求解操作，我们需要先利用下标进行一个转换操作。以下面这组用例为例：

4
    CABC
    CCAB

我们先对 A 编号，并按字符提取下标：

1 2 3 4
    C A B C
    =>
    A: 2
    B: 3
    C: 1 4

接着，我们根据提取的下标对字符串 B 进行编号：

C C A B
    =>
    1 4 2 3

最后，我们可以通过对数列 `1 4 2 3` 求逆序对得到答案啦~

# 参考代码 #

求逆序对常用的方法有两种，一种是归并排序，在合并的时候用 `ans += mid - i + 1` 进行求解；另一种是树状数组，遍历数组时用`ans += i - sum(a[i])` 求解。

## 1. 归并排序 ##

#include <iostream>
    #include <cstring>
    #include <vector>
    using namespace std;
    const int maxn = 1e6 + 10;
    long long ans, n;
    // lt[i]表示字母(i+'A')访问到st[i]的下标
    // a[] 表示处理之后元素值各不相同的数组，temp[] 是归并过程中用到的中间数组
    int lt[26], a[maxn], temp[maxn];
    vector<int> st[26]; // st[i][j] 表示第j个字母(i+'A')所在的下标
    string strA, strB;
    
    void mergeSort(int left, int right) { 
        if (left == right) { 
            return ;
        }
        int mid = left + (right - left) / 2;
        int i = left, j = mid + 1, k = left;
        mergeSort(left, mid);
        mergeSort(mid + 1, right);
        while (i <= mid && j <= right) { 
            if (a[i] <= a[j]) { 
                temp[k++] = a[i++];
            } else { 
                temp[k++] = a[j++];
                ans += mid - i + 1; // 求逆序对
            }
        }
        while (i <= mid) { 
            temp[k++] = a[i++];
        }
        while (j <= right) { 
            temp[k++] = a[j++];
        }
        for (int l = left; l <= right; l++) { 
            a[l] = temp[l];
        }
    }
    
    int main()
    { 
        cin >> n;
        cin >> strA >> strB;
        for (int i = 0; i < n; i++) { 
            int idx = strA[i] - 'A';
            st[idx].push_back(i + 1);
        }
        for (int i = 0; i < n; i++) { 
            int idx = strB[i] - 'A';
            a[i + 1] = st[idx][lt[idx]++];
        }
        mergeSort(1, n);
        cout << ans << endl;
        return 0;
    }

## 2. 树状数组 ##

#include <iostream>
    #include <cstring>
    #include <vector>
    using namespace std;
    const int maxn = 1e6 + 10;
    long long ans, n;
    // lt[i]表示字母(i+'A')访问到st[i]的下标
    // a[] 表示处理之后元素值各不相同的数组，temp[] 是归并过程中用到的中间数组
    int lt[26], a[maxn], c[maxn];
    vector<int> st[26]; // st[i][j] 表示第j个字母(i+'A')所在的下标
    string strA, strB;
    
    int lowbit(int x) { 
        return x & (-x);
    }
    
    void update(int i, int x) { 
        for ( ; i <= n; i += lowbit(i))
            c[i] += x;
    }
    
    int sum(int i) { 
        int res = 0;
        for ( ; i >= 1; i -= lowbit(i))
            res += c[i];
        return res;
    }
    
    int main()
    { 
        cin >> n;
        cin >> strA >> strB;
        for (int i = 0; i < n; i++) { 
            int idx = strA[i] - 'A';
            st[idx].push_back(i + 1);
        }
        for (int i = 0; i < n; i++) { 
            int idx = strB[i] - 'A';
            a[i + 1] = st[idx][lt[idx]++];
        }
        for (int i = 1; i <= n; i++) { 
            update(a[i], 1);
            ans += i - sum(a[i]);  // 求逆序对
        }
        cout << ans << endl;
        return 0;
    }

[https_www.luogu.com.cn_problem_P3531]: https://www.luogu.com.cn/problem/P3531