[NOIP 2013 提高组] 火柴排队

GitHub跳转原题关系图返回列表

按高度排名建立两列位置的对应排列，再把最少相邻交换次数转成逆序对。

OJ: luogu

题目 ID: P1966

难度:提高+/省选-

标签:排序树状数组逆序对python

日期: 2026-07-16 18:28

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

两列火柴内部都可以交换相邻元素。先让两列对应位置的高度平方差之和最小，再求达到该最小值所需的最少交换次数。

思路

根据排序不等式，最小距离一定来自“第 rr 小和第 rr 小配对”。因此先分别得到两列下标按高度递增的顺序，再用 zip 把相同排名的两根火柴配对。

令 target[i] 表示第一列位置 i 最终应对应第二列的哪个位置。现在问题变成：通过相邻交换把一个排列调整到 target 的顺序。一个相邻交换恰好改变一个逆序对，所以最少交换次数就是 target 的逆序对数。

最后用树状数组从左到右统计逆序对，并按题意取模。

Python 知识

  • sorted(range(n), key=first.__getitem__) 排序的是下标，而不是复制 (值, 下标) 元组。
  • list.__getitem__ 可以直接充当 key，比只做下标访问的 lambda 更简洁。
  • zip(order_a, order_b) 能自然表达“把相同排名配成一对”。
  • Python 整数不会溢出，可以最后统一 % MOD。

代码

python
import sys


MOD = 10**8 - 3
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
first = [next(data) for _ in range(n)]
second = [next(data) for _ in range(n)]
target = [0] * n

for first_index, second_index in zip(
    sorted(range(n), key=first.__getitem__),
    sorted(range(n), key=second.__getitem__),
):
    target[first_index] = second_index

tree = [0] * (n + 1)
answer = 0
for seen, position in enumerate(target):
    index = position + 1
    prefix = 0
    i = index
    while i:
        prefix += tree[i]
        i -= i & -i
    answer += seen - prefix
    while index <= n:
        tree[index] += 1
        index += index & -index

print(answer % MOD)

复杂度

两次排序与树状数组统计都是 O(nlog⁡n)O(n\log n)，空间 O(n)O(n)。

总结

本题有两次转化：最小平方差决定“相同排名配对”，最少相邻交换又等于目标排列的逆序对数。