北京海淀区信息学竞赛 · 2023 北京市海淀区信息学竞赛（初赛）试题 第 11 题

在数组 $A[x]$ 中，若存在 $(i < j) \land (A[i] > A[j])$，则称 $(A[i], A[j])$ 为数组 $A[x]$ 的一个逆序对。对于序列 $7, 5, 1, 9, 3, 6, 8, 4$，在不改变顺序的情况下，去掉（ ）会使逆序对的个数减少 $3$。

这题考逆序对个数变化，拿到题先算原序列逆序对总数，再逐个删选项数新逆序对，差值=3 的即为答案。

学生常把逆序对定义记反（以为 i>j 才叫逆序对），或者算总数时漏数，导致差值算错；还有人选错后不验证，直接凭感觉排除，容易把正确答案当干扰项丢下。

逆序对与删数效应

考点与概念

逆序对就是数组里前面比后面大的那对数。比如 7,5,1 中 (7,5)、(7,1)、(5,1) 都是逆序对。删掉一个数，只会影响那些被删数参与的逆序对，其他数之间的相对大小不变。