\(\mathtt{Link}\)

传送门

\(\mathtt{Summarization}\)

给定两个长度都为 \(n\) 的序列，求交换两个数组中相邻数，使得 \(\sum_{i=1}^n(a_i-b_i)^2\) 最小化的最小步数。

\(\mathtt{Solution}\)

这题分为两个部分，

• 第一个部分是，使得 \(\sum_{i=1}^n(a_i-b_i)^2\) 最小化的顺序是什么？
• 第二个部分是，调整到这种顺序最少需要多少步？

那咱们先解决第一个部分再来解决第二个部分：

\(\mathcal{Part 1}\)

看这个式子觉得毫无头绪，不如咱们用完全平方差拆开一下这个式子：

显然，无论怎么调整 \(a\) 和 \(b\) 的顺序，\(\sum_{i=1}^n{a_i} ^ 2 + \sum_{i=1}^n{b_i} ^ 2\) 总是定值。因此，题目要求的式子的值只与 \(\sum_{i=1}^na_ib_i\) 有关，也就是要让这个式子取最大值。(注意是最大值，不是最小值。因为原式子中是减它)

有一个定理，当 \(a\)，\(b\) 中对于每一个位置 \(i\) 都有 \(a_i\) 是 \(a\) 中第 \(k\) 小的，而 \(b_i\) 也是 \(b\) 中第 \(k\) 小的时，\(\sum_{i=1}^na_ib_i\) 最大。(本题已经规定所有火柴高度都是正整数了)

简证：(默认 \(a, b\) 所有数都是正整数，因为数据范围已经体现)取 \(a_1 \le a_2, b_1 \le b_2\)， 可得 \(a_2(b_2-b_1) \ge a_1(b_2-b_1)\)。把这个式子变一下形可以得到：\(a_1b_1+a_2b_2 \ge a_1b_2+a_2b_1\)。推广这个结论到多个数便可以得到结论了。

好，现在我们已经知道最优的情况是怎么排列了，让同一个位置的两个数组中的数在原数组中的大小地位相同即可。那么调换的最小步数又该怎么求呢？我们进入第二部分：

\(\mathcal{Part2}\)

我们可以考虑这样一种做法，

• 记录每个火柴(数字)的编号和地位。(编号指之前在这个序列的第几号，地位指是这个序列的第几小的)(此处可以用结构体实现，待会code实现就明白了)
• 定义一个新数组 \(q\)，规定下标为 A火柴中地位为 \(i\) 的编号 的值为B火柴中地位为 \(i\) 的编号。那么 \(q\) 数组中的逆序对数量就是答案。

估计你此刻一定有114514个问题要问，别急，蟹蟹举个例子慢慢说。

就按照样例1来吧：

2 3 1 4
3 2 1 4

那么将 \(a, b\) 排序，此时位于第 \(i\) 个位置上的数就是地位为 \(i\) 的数了。

排序后进行处理：

2 3 1 4 -> 1 2 3 4 -> 原编号：3 1 2 4
3 2 1 4 -> 1 2 3 4 -> 原编号：3 2 1 4

牢记这个式子：q[a[i].num] = b[i].num;

可得

q[a[1].num] = b[1].num -> q[3] = 3
q[a[2].num] = b[2].num -> q[1] = 2
q[a[3].num] = b[3].num -> q[2] = 1
q[a[4].num] = b[4].num -> q[4] = 4

q数组的值分别为：2 1 3 4

q数组中共有1个逆序对(2， 1)

因此答案为 1

好，现在你应该理解这个方法是什么意思了，接下来我们来看为什么这样做是对的。

首先，我们来看逆序对的定义。

\(i < j, a_i > a_j\)

转化为此题中的 \(q\) 数组，就可以说a[i].num > a[j].num, b[i].num < b[j].num。这说明了什么？我们以a为基准调整b，那么b[i]和b[j]的顺序就是反的，需要别过来。

还有一个定理，如果要让有 \(p\) 个逆序对的序列通过两两交换变成上升序列，那么需要操作 \(p\) 次。(可以从必有逆序对紧挨定理得出，每次交换紧挨的逆序对即可)

那么就可以得出答案就和 \(q\) 数组逆序对数量相等了。

如何求逆序对数量？

https://www.luogu.com.cn/problem/P1908

\(\mathtt{Code}\)

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2020-11-01 17:04:02 
 * @Last Modified by:   crab-in-the-northeast 
 * @Last Modified time: 2020-11-01 17:04:02 
 */
#include <iostream>
#include <cstdio>
#include <algorithm>

const int maxn = 100005;
const int mod = (int)1e8 - 3;

struct match {
    int height;
    int num;
    const bool operator < (match &b) {
        return this -> height < b.height;
    }
}a[maxn], b[maxn];

long long ans = 0;
int q[maxn], tmp[maxn];

void merge_sort(int l, int r) {
    if (l == r)
        return ;
    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else {
            tmp[k++] = q[j++];
            ans = (ans - i + mid + 1) % mod;
        }
    }

    while (i <= mid)
        tmp[k++] = q[i++];
    while (j <= r)
        tmp[k++] = q[j++];
    
    for (int i = l; i <= r; ++i)
        q[i] = tmp[i];
    return ;
}

int main() {
    int n;
    std :: scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        std :: scanf("%d", &a[i].height);
    for (int i = 1; i <= n; ++i)
        std :: scanf("%d", &b[i].height);
    for (int i = 1; i <= n; ++i)
        a[i].num = b[i].num = i;
    
    std :: sort(a + 1, a + 1 + n);
    std :: sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; ++i)
        q[a[i].num] = b[i].num;
    merge_sort(1, n);
    std :: printf("%lld\n", ans);
    return 0;
}

\(\mathtt{More}\)

这种问题一看就是要分Part讨论的，要注意分Part讨论的题一定不要合在一起讨论。不然你会乱！！

然后看到相邻交换使得序列有序之类的，就要从逆序对数量这个角度考虑了。(虽然这种情况有点特殊)