NOIP 普及 2017 第一轮 第 11 题：给定序列的逆序对数量

题目

对于给定的序列 $\{a_k\}$，我们把 $(i,j)$ 称为逆序对当且仅当 $i < j$ 且 $a_i > a_j$。那么序列 $1, 7, 2, 3, 5, 4$ 的逆序对数为（ ）个。

选项

• A. 4
• B. 5
• C. 6
• D. 7

答案

B

题解

考点定位

本题考「逆序对计数」,对应大纲 2.1.5（难度【2】）。

解题过程

1,7,2,3,5,4：逆序对 (7,2),(7,3),(7,4)? 7 后面比它小：2,3,5,4 → 4 个；(5,4) → 1 个。合计 5。

选 B。

易错提醒

① 逐元素数「后面比它小」；② 归并排序可 O(n log n) 计数。