1349.[NOIP2013 提高组] 火柴排队

算法思路

1. 问题分析

题目要求最小化两列火柴的距离 $\sum(a_i - b_i)^2$，等价于最大化 $\sum a_i b_i$。根据排序不等式，当两个序列均为升序（或降序）排列时，乘积和最大。因此，问题转化为通过交换相邻火柴使两个序列的排名顺序一致（即第一个序列中第 $k$ 小的火柴与第二个序列中第 $k$ 小的火柴位置对齐）。最小交换次数等价于第二个序列按第一个序列排名规则构成的序列的逆序对数。

2. 解决策略

1. 离散化排名：分别对两个序列排序，记录每个元素的原始位置。
2. 构建映射数组：将第二个序列中排名为 $i$ 的元素原始位置映射到第一个序列中排名为 $i$ 的元素原始位置。
3. 计算逆序对：对映射数组进行归并排序，统计逆序对数量（即最小交换次数）。
4. 取模处理：结果对 $10^8-3$（99999997）取模。

3. 复杂度分析

• 时间复杂度：$O(n \log n)$。排序离散化 $O(n \log n)$，归并排序求逆序对 $O(n \log n)$。
• 空间复杂度：$O(n)$。存储映射数组和临时归并数组。

---

代码实现

C++解法

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4const int mod = 99999997;
5const int MAXN = 1000005;
6long long n, x[MAXN], p[MAXN], ans = 0;
7
8struct Fire {
9    int hi, bh;  // 火柴高度和原始位置
10} l1[MAXN], l2[MAXN];
11
12// 比较函数：按高度升序排序
13bool cmp1(Fire a, Fire b) {
14    return a.hi < b.hi;
15}
16
17// 归并排序：计算逆序对
18void msort(int s, int t) {
19    if (s == t) return;
20    int mid = (s + t) / 2;
21    msort(s, mid);
22    msort(mid + 1, t);
23    int i = s, j = mid + 1, k = s;
24    while (i <= mid && j <= t) {
25        if (x[i] <= x[j]) {
26            p[k++] = x[i++];  // 无逆序
27        } else {
28            p[k++] = x[j++];
29            // 左半部分剩余元素均与x[j]构成逆序对
30            ans = (ans + mid - i + 1) % mod;  // 累加逆序对数量
31        }
32    }
33    while (i <= mid) p[k++] = x[i++];  // 处理剩余元素
34    while (j <= t) p[k++] = x[j++];
35    for (int i = s; i <= t; i++) x[i] = p[i];  // 写回原数组
36}
37
38int main() {
39    scanf("%lld", &n);
40    for (int i = 1; i <= n; i++) {
41        scanf("%d", &l1[i].hi);
42        l1[i].bh = i;  // 记录原始位置
43    }
44    for (int i = 1; i <= n; i++) {
45        scanf("%d", &l2[i].hi);
46        l2[i].bh = i;
47    }
48    // 按高度升序排序
49    sort(l1 + 1, l1 + n + 1, cmp1);
50    sort(l2 + 1, l2 + n + 1, cmp1);
51    // 构建映射：x[第二个序列位置] = 第一个序列对应排名的位置
52    for (int i = 1; i <= n; i++) {
53        x[l2[i].bh] = l1[i].bh;
54    }
55    msort(1, n);  // 计算逆序对
56    printf("%lld", ans);
57    return 0;
58}

代码解释：

• 映射构建：x[l2[i].bh] = l1[i].bh 将第二个序列的原始位置映射到第一个序列的对应排名位置。
• 逆序对计算：归并排序中，当右半部分元素小于左半部分当前元素时，左半部分剩余元素均与其构成逆序对。
• 边界处理：数组下标从1开始，严格对应火柴原始位置。

Python3解法

python
复制
1MOD = 99999997
2
3def main():
4    n = int(input())
5    a_list = list(map(int, input().split()))
6    b_list = list(map(int, input().split()))
7    
8    # 创建元组列表（高度，原始位置）
9    fires_a = [(val, idx + 1) for idx, val in enumerate(a_list)]
10    fires_b = [(val, idx + 1) for idx, val in enumerate(b_list)]
11    
12    # 按高度排序
13    fires_a.sort(key=lambda x: x[0])
14    fires_b.sort(key=lambda x: x[0])
15    
16    # 构建映射数组：x[第二个序列位置] = 第一个序列对应位置
17    x = [0] * (n + 1)
18    for i in range(n):
19        pos_in_b = fires_b[i][1]  # 第二个序列第i小元素的原始位置
20        x[pos_in_b] = fires_a[i][1]  # 映射到第一个序列第i小元素的原始位置
21    
22    # 提取x[1..n]并计算逆序对
23    arr = [x[i] for i in range(1, n + 1)]
24    
25    def merge_sort(arr, left, right):
26        if left >= right:
27            return 0
28        mid = (left + right) // 2
29        inv_count = merge_sort(arr, left, mid) + merge_sort(arr, mid + 1, right)
30        temp = []
31        i, j = left, mid + 1
32        while i <= mid and j <= right:
33            if arr[i] <= arr[j]:
34                temp.append(arr[i])
35                i += 1
36            else:
37                temp.append(arr[j])
38                j += 1
39                # 左半部分剩余元素均构成逆序对
40                inv_count = (inv_count + mid - i + 1) % MOD
41        # 添加剩余元素
42        temp.extend(arr[i:mid + 1])
43        temp.extend(arr[j:right + 1])
44        # 更新原数组
45        arr[left:right + 1] = temp
46        return inv_count % MOD
47
48    result = merge_sort(arr, 0, n - 1)
49    print(result)
50
51if __name__ == "__main__":
52    main()

代码解释：

• 与C++差异：使用元组代替结构体，通过列表切片简化数组合并。
• 关键逻辑：merge_sort中mid - i + 1计算左半部分剩余元素数量（均构成逆序对）。
• Python特性：利用extend高效合并剩余元素，避免显式循环。

---

复杂度对比

场景建议：

• C++：适用于$n \geq 10^6$的高性能场景（如竞赛）。
• Python：适用于$n \leq 10^5$的快速原型开发或脚本场景。