题目描述

难度:[蓝]提高+/省选-

输入$n(1 \leq n \leq 10^5)$和两个长为$n$的数组$a$和$b$，元素范围$[0,2^{31})$。保证$a$中没有重复元素，$b$中没有重复元素。

每次操作，你可以交换$a$中的一对相邻元素，或者$b$中的一对相邻元素。

为了最小化$(a[i]-b[i])^2$之和，至少要操作多少次？

输出最小操作次数模$10^8-3$的结果。

输入样例$1$

4
2 3 1 4
3 2 1 4

输出样例$1$

4
1 3 4 2
1 7 2 4

输入样例$2$

输出样例$2$

2

算法

归并排序

比较容易发现两个性质：

1. 可以交换$a$中元素或者$b$中元素，但是实际上只要交换一个数组中的元素就可以了。
2. 假设交换$b$中的元素，那么根据排序不等式，让$b[i]$和$a[i]$分别在自己所在数组的排名相同，就能使得$\Sigma_{i \in [1,n]}(a[i]-b[i])^2$最小。

因此先将$a$和$b$备份到$A$和$B$中，分别将$A$和$B$排序。然后遍历$A$和$B$，构建一个哈希映射$match$，$match[A[i]]=B[i]$表示$(A[i],B[i])$是配对的。再遍历$b$数组构建一个哈希映射$val2pos$，其中$val2pos[b[i]]=i$。

遍历$a$，构建一个$nums$数组，$nums[i]=val2pos[match[a[i]]]$，意思就是$a$的$i$位置要放$b$索引$val2pos[match[a[i]]]$位置上的数。这样我们的问题就变成将$nums$数组排好序最少需要几次交换？直接求一下$nums$的逆序对数量就可以了，可以用树状数组或者归并排序来求。

复杂度分析

时间复杂度

对两个排序备份数组$A$和$B$排序的时间复杂度为$O(nlog_2n)$；预处理出两个哈希表$val2pos$和$match$的时间复杂度为$match$；最后归并排序求答案的时间复杂度为$O(nlog_2n)$。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

排序备份数组的空间消耗是$O(n)$；两个哈希表$val2pos$和$match$中存了$O(n)$个键值对，空间复杂度为$O(n)$；归并排序的空间复杂度为$O(n)$。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010, MOD = 1e8 - 3;
int n, a[N], b[N], A[N], B[N];
long long cnt;

void merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> help(right - left + 1, 0);
    int i = left, j = mid + 1, index = 0;
    while(i <= mid && j <= right) {
        if(nums[i] <= nums[j]) {
            help[index++] = nums[i++];
        }else {
            help[index++] = nums[j++];
            cnt += mid - i + 1;
        }
    }
    while(i <= mid) {
        help[index++] = nums[i++];
    }
    while(j <= right) {
        help[index++] = nums[j++];
    }
    for(int i = 0; i < help.size(); i++) {
        nums[left + i] = help[i];
    }
}

void merge_sort(vector<int>& nums, int left, int right) {
    if(left >= right) {
        return;
    }
    int mid = left + ((right - left) >> 1);
    merge_sort(nums, left, mid);
    merge_sort(nums, mid + 1, right);
    merge(nums, left, mid, right);
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        A[i] = a[i];
    }
    unordered_map<int, int> val2pos;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        B[i] = b[i];
        val2pos[b[i]] = i;
    }
    sort(A + 1, A + n + 1);
    sort(B + 1, B + n + 1);
    unordered_map<int, int> match;
    for(int i = 1; i <= n; i++) {
        match[A[i]] = B[i];
    }
    vector<int> nums;
    for(int i = 1; i <= n; i++) {
        nums.push_back(val2pos[match[a[i]]]);
    }
    cnt = 0;
    merge_sort(nums, 0, n - 1);
    printf("%d\n", cnt % MOD);
    return 0;
}