[NOIP2013 提高组] 火柴排队

题目

题目背景

NOIP2013 提高组 D1T2

题目描述

涵涵有两盒火柴，每盒装有 $n$ 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：

$$ \sum (a_i-b_i)^2 $$

其中$a_i$ 表示第一列火柴中第 $i$ 个火柴的高度，$b_i$ 表示第二列火柴中第 $i$ 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 $10^8-3$ 取模的结果。

输入格式

共三行，第一行包含一个整数 $n$，表示每盒中火柴的数目。

第二行有 $n$ 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有 $n$ 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

输出格式

一个整数，表示最少交换次数对 $10^8-3$ 取模的结果。

样例 #1

样例输入 #1

4
2 3 1 4
3 2 1 4

样例输出 #1

1

样例 #2

样例输入 #2

4
1 3 4 2
1 7 2 4

样例输出 #2

2

提示

输入输出样例说明一

最小距离是 $ 0$，最少需要交换 $1$ 次，比如：交换第 $1 $ 列的前 $ 2$ 根火柴或者交换第 $2$ 列的前 $2 $ 根火柴。

输入输出样例说明二

最小距离是 $10$，最少需要交换 $2$ 次，比如：交换第 $1$ 列的中间 $2$ 根火柴的位置，再交换第 $2$ 列中后 $2$ 根火柴的位置。

数据范围

对于 10% 的数据， 1 <= n <= 10；

对于 30% 的数据，1 <= n <=100；

对于 60% 的数据，1 <= n <= 1000;

对于 100% 的数据，1 <= n <= 100000，0 <= 火柴高度 < 2^31。

解题思路

问题一：什么情况下两盒火柴距离最小？

问题二：多少次移动可以达到距离最小？

解决问题一时不要考虑问题二，解决问题一时可以随意改变火柴顺序，解决问题二时需要根据题目限制移动火柴。理解解题思路时不要考虑具体实现。

解决问题一:

结论： 将两盒火柴排序，排序后每一对序号相同的火柴$a_i$,$b_i$，保持坐标相同时，两盒火柴距离最小。也就是说当两盒火柴中，所有高度排序相同的火柴，下标都相等时，两盒火柴距离最小。

证明： 题目要求我们最小化$\sum (a_i-b_i)^2$ ，首先第一个给我们的启示是：遇到这种相互约束的式子，我们可以考虑将其拆开，变成容易维护的式子。

因为$\sum\left(a_{i}-b_{i}\right)^{2}=\sum\left(a_{i}^{2}+b_{i}^{2}\right)-2 \times \sum a_{i} \times b_{i}$。前者显然是一个定值，我们要求的就是$\sum a_i \times b_i$的最大值。高中数学选修4−5里面有一个不等式叫排序不等式（所以数学是很重要的！）： 若 $ a_ {1} \leqslant a_ {2} \leqslant a_ {3} \leqslant \cdots \leqslant a_ {n} $ 与 $ b_ {1} \leqslant b_ {2} \leqslant b_ {3} \leqslant \cdots \leqslant b_ {n} $ 那么有 $a_ {1} b_ {n} + a_ {2} b_ {n-1} + \cdots + a_ {n} b_ {1} \leqslant a_ {i1} b_ {i1} + a_ {i2b_ {i2}} + \cdots + a_ {in} b_ {in} \leqslant a_ {1} b_ {1} + a_ {2} b_ {2} + \cdots + a_ {n} b_ {n} $ 即反序和$\leqslant$乱序和$\leqslant$同序和。

解释: 将距离降低到最小值的过程就是将排名相同的火柴配对的过程。

解决问题二：

现在已经知道了最优解的情形应该满足的条件，现在需要反推实现过程。首先根据前面的分析可以知道，我们对于每个火柴实际高度并不关心，我们只关心火柴在他的队列中的排名，也就是说我们只关注相对大小而不在乎绝对大小。那我们可以让问题变得简单一点，我们可以将火柴的高度重新赋值为它在它的队列中的高度排名，这样既保留了相对大小的不变，也可以让值域降低到0到n-1的范围。由于同一列火柴的高度互不相同，所以是不存在并列排名的情况的。这是离散化的过程，后续理解起来更简单，其实这一步不做也可以。做完离散化后，问题就变成了，移动a,b数组中的元素，让这两个数组变得一样。

然后思考，问题应该如何简化。

1. 对两个数组都执行交换操作，可以简化成保持一组数组不变，只在一个数组中进行交换。感性的认识，假设我们每一步移动都是全局最佳的，在a中移动一步，则向a与b相同的目标移动了一步；等价于在b中移动一步，使得b与a相同的目标移动了一步。可以理解成a数组规定了一个目标顺序，移动b数组元素使得b数组顺序与a数组相同。
2. a数组规定了一个任意顺序，可以将这个任意顺序等价转换成自然的递增顺序。为了完成这个转换，可以理解为a数组规定的顺序，重新定义了数的大小关系，举例说明 $a \left \{ 1,0,2 \right \}\quad b \left \{ 2,1,0 \right \} $ ，即a规定了1 < 0 < 2，将1替换成x，0替换成y，2替换成z，这两个数组就变成了 $a' \left \{ x,y,z \right \}\quad b' \left \{ z,x,y \right \} $ ，让a', b'数组通过交换变得相同，与原问题a, b数组通过交换变得相同，是完全等价的。再将a', b'中的x替换成0，y替换成1，z替换成2，得到 $a'' \left \{ 0,1,2 \right \}\quad b'' \left \{ 2,0,1 \right \}$ ，同理a'', b''也与a', b'等价，那么a, b实际上也就和a'', b''也是等价的，它们本质上是同一个问题，但是转化成a'', b''的形式是有利于我们理解和编程的。

问题简化至此，已经变成了一个非常熟悉的问题。a''数组规定了一个数字自然升序的顺序，那我们就可以丢掉a''数组，只考虑b''数组了，由于等价性，后续将b''数组直接称为b数组。现在我们需要解决的问题是，将b数组成变为与a数组规定的自然升序数组相同的数组，也就是将b排序，每次只能移动相邻的两个元素，最少需要移动几次？这个问题就是经典的逆序对问题，对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i < j$ 的有序对。逆序对数量等于排序的最小步数，逆序对的数量描述了序列与有序序列的距离。题目规定的一次相邻元素交换操作即是一步，如果每步都是全局最佳的一步，那么便可用最小的步数使得b数组有序。因此只要求出b数组中逆序对的数量，这个数量就是完成排序所需要的最少步数。

代码实现

// https://www.luogu.com.cn/problem/P1966
// https://www.acwing.com/problem/content/507/ 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;

const LL p = 99999997;
const int N = 100010;
 
int n;
// a,b: 为了解决问题1需要获得每一元素的排序信息，但排序后还需要保持原下标信息，因此使用pair.second存储原始下标 
pair<int,int> a[N],b[N];
// q: 简化2中，转换完成的b数组 --- b'' 数组 
int q[N];
// ans: 逆序对个数即为最小交换次数
LL ans;  

void merge(int left,int mid,int right)
{
    vector<int> ta;
    int i = left, j = mid + 1;
    while (i <= mid && j <= right)
    {
        if (q[i] < q[j])
        {
            ta.push_back(q[i]);
            i++;
        }
        else if (q[i] > q[j]) 
        {
            // q[i] > q[j]时q[i]-q[mid]的所有元素与q[j]形成逆序对 
            ans = (ans + (LL)(mid - i + 1)) % p; 
            ta.push_back(q[j]);
            j++;
        }
    }
    if (i > mid)
    {
        while (j <= right) 
        {
            ta.push_back(q[j]);
            j++;
        }
    }
    else if (j > right)
    {
        while (i <= mid)
        {
            ta.push_back(q[i]);
            i++;
        }
    }
    for (int x = left;x <= right;x++)
    {
        q[x] = ta[x - left];
    }
}

void mergeSort(int left, int right) // 归并排序 
{
    if (left == right) return;
    int mid = (left + right) >> 1;
    mergeSort (left,mid);
    mergeSort (mid+1,right);
    merge(left,mid,right);
}

int main()
{
    cin >> n;
    for (int i = 0;i < 2;i++)
    {
        pair<int,int>* c = a;
        if (i == 1) c = b;
        for (int j = 0;j < n;j++)
        {
            int temp;
            cin >> temp;
            c[j] = {temp,j};
        }
    }
    sort(a,a+n);
    sort(b,b+n);
    for (int i = 0;i < n;i++)
    {
        // b[i].second为b[i]项原下标; a[i].second为b[i]项目标位置或离散化后的大小 
        q[b[i].second] = a[i].second;  
    }
    // 对q归并排序并计算逆序对个数
    mergeSort(0,n-1);
    cout << ans;
    return 0;
}

相关链接

1. 本文数学证明来自[Asika39 - [NOIP2013] 火柴排队 题解](https://www.luogu.com.cn/article/m5d1srug)
2. 逆序对 - Wikipedia
3. 逆序对计数方法详解参见 算法篇：逆序对_逆序对算法-CSDN博客
4. 题目链接：洛谷 AcWing