题目
分析
要解决这个问题，需要用到一个数学知识。根据题意，我们是求\(\sum (a_i-b_i)^2\)的最小值。展开后就是求：\(\sum a_i^2+b_i^2-2a_ib_i\)的最小值。由于每根火柴的高度是确定了的,所以，该问题就转化为求\(\sum a_ib_i\)的最大值。
这里给出直接结论：假定\(a, b\)是两个已经排好序的数组，那么依次从头到尾一一对应地选择两个数组中的元素，一定可以得到最大的\(\sum a_ib_i\)。
从这里可以得到一个洞见：不需要直接去“重排”原数组。原因是：我们只要把数组A的“顺序”当作目标顺序（不改变它在内存中的相对位置），再把B数组按照数值排序后与A按“数值排名”一一配对，等价于把两组中每个位置的元素按从小到大对应配对，从而得到最大的\(\sum a_ib_i\)（即最小的\(\sum (a_i-b_i)^2\)）。
用图表说明就是：
位置 1 2 3 4
A数组 2 3 1 4
B数组 3 2 1 4从A要求的位置来看，2在1号位，3在2号位。用这个位置关系映射到B数组，现在的位置是2-1（对应数字3-2`）。要发生一次交换。
怎样统计这种交换次数，我们在本章前两个例题（P1177和P1908）中已经有说明。
分解步骤如下。
输入、建立索引数组
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < n; i++)
{
cin >> b[i];
}
// 创建索引数组，idx[i]表示第i小的数字在原数组中的位置
vector<int> idx_a(n), idx_b(n);
for (int i = 0; i < n; i++)
{
idx_a[i] = i;
idx_b[i] = i;
}按照值来排序索引
我们在idx_a和idx_b中存放的是标准索引，但需要根据各自的值来排序索引！
sort(idx_a.begin(), idx_a.end(), [&](int x, int y) { return a[x] < a[y]; });
sort(idx_b.begin(), idx_b.end(), [&](int x, int y) { return b[x] < b[y]; });注意，这里我们竟然是根据a/b数组的值，来排序idx_a/idx_b！结果就是：idx_a[0]是数组a中最小元素的位置，以此类推。
设定目标排序
idx_a和idx_b两个“索引”数组建立后，我们要建立一个映射关系：idx_a[i]上要放置idx_b[i]。注意，我们这里避免了实际数值的映射，而是映射了两个数组值的大小的位置关系。
// 创建目标数组：在位置idx_a[i]放置idx_b[i]
vector<int> target_array(n);
for (int i = 0; i < n; i++)
{
target_array[idx_a[i]] = idx_b[i];
}归并排序求交换次数
最后，用我们熟悉的归并排序统计逆序对。对答案按题意取模，本题模数为99999997。
- 构造出的
target_array就是把B重排成与A“数值排名”一致所需的目标顺序。 - 在
target_array上统计逆序对的个数，即为最少相邻交换次数。 - 题目保证“同一列火柴的高度互不相同”，因此此处简单按值排序即可。
答案
思考
这道题很绕。有很多细节需要想清楚。
从洞见出发，想到对“位置”进行整理，是本题的核心关键。
再补充两点易错处：
- 若遇到拓展题里存在“同一列可能有相等值”的情况，需要使用稳定排序或用下标打破平局；但本题不需要（同列互不相同）。
- 统计逆序对时请使用64位累加，过程中按
MOD=99999997取模，以防溢出并满足题意输出要求。
复杂度分析
- 时间复杂度：\(O(n log n)\)。主要开销在按值排序索引与归并统计逆序对/树状数组操作。
- 空间复杂度：\(O(n)\)。使用了索引数组、目标数组与归并的辅助数组（或 BIT）。
为什么等于逆序对
- 通过按值排序后的
idx_a和idx_b建立映射：在位置idx_a[i]放置idx_b[i]，得到目标数组target_array。 - 将
target_array看作一个排列（相对于有序位置的映射）。把该排列通过相邻交换复原为升序，所需的最少相邻交换次数，恰是其中的逆序对个数。 - 直观理解：每次相邻交换至多消去一个逆序对；而任何把序列变有序的过程至少要消去所有逆序对，因此下界与上界相等，即最少相邻交换次数 = 逆序对数。
术语备注
- 理论依据是“重排不等式”（Rearrangement Inequality）：同序配对使得\(\sum a_ib_i\)最大，反序最小。本题把“按数值排名的同序配对”通过位置映射与相邻交换实现。