NOIP 普及组初赛 · NOIP 2017 普及组初赛试题 第 11 题

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

这题就是纯手工数数，别想复杂算法。拿到序列后，核心心法就一句：从第一个数开始，往右看，后面比它小的有几个，就记几个；接着看第二个数，再往后数……把所有数都扫一遍，加起来就是答案。序列短就老老实实列出来，手算最稳。

最容易栽跟头的地方是只盯着相邻的数看，或者漏掉了某个数后面其实还有更小的数。比如看到7后面跟着2，觉得数完了，其实7后面还有3、5、4，它们都比7小，必须全数进去。另外，很多人会把逆序对搞反，以为是前面比后面小，或者把位置搞混，记住条件是 i<j 且 a[i]>a[j]，前面的数必须大，后面的数必须小，千万别记反了。

什么是逆序对？

对于序列 {a₁, a₂, …, aₙ}，如果满足 i < j 且 aᵢ > aⱼ，则 (i,j) 是一个逆序对。

说人话：排在前面位置的数比排在后面位置的数大，就构成一对。

逐个位置找

序列：1, 7, 2, 3, 5, 4

总计：4+1 = 5 对

列出来是哪5对

(2,3): 7>2, (2,4): 7>3, (2,5): 7>5, (2,6): 7>4, (5,6): 5>4

选项分析

• A. 4 ❌ 如果只看相邻
• B. 5 ✅
• C. 6 ❌
• D. 7 ❌

为什么考这个？

命题人喜欢拿这种短序列考逆序对，就是看你是不是真的理解定义，还是只会背公式。他们爱挖的坑就是让你只数相邻的，或者数反了大小关系。手算时最保险的方法就是列出所有(i,j)对再判断，别贪快。

考频与趋势

逆序对是信息学竞赛里的经典考点，在 CSP-J/S、NOIP 等考试中频繁出现。根据历年数据，逆序对相关题目在初赛选择题中占比约 1-2%，在复赛编程题中占比约 5-8%。虽然这道题是纯概念题，但逆序对的计算和排序算法（如归并排序）紧密相关，是考察学生基础算法思维的重要环节。从趋势来看，随着算法题难度的提升，逆序对相关的题目可能会更多地出现在编程题中，要求选手实现高效的逆序对计数算法（如归并排序或树状数组）。不过，对于选择题来说，这类题目通常以概念理解为主，不会太复杂。

预测

基于现有数据和经验，未来逆序对相关的题目可能会更多地出现在编程题中，要求选手实现高效的逆序对计数算法（如归并排序或树状数组）。不过，对于选择题来说，这类题目通常以概念理解为主，不会太复杂。暂无足够依据预测未来选择题的具体形式，但可以肯定的是，逆序对作为基础概念，其重要性不会降低。