NOIP 提高 2011 第一轮 第 17 题：对于序列“7、5、1、9、3、6、8、4”，在不改变顺序的情况下，去掉（）会使逆

题目

对于序列 $7,5,1,9,3,6,8,4$，在不改变顺序的情况下，去掉（   ）会使逆序对的个数减少 $3$。

答案

C、D

题解

考点定位

本题考「逆序对贡献分析（不定项）」,对应大纲 2.1.5 逆序对（难度【4】）。

解题过程

序列 7,5,1,9,3,6,8,4。去掉一个元素减少的逆序对数 = 该元素参与的逆序对数（与两侧元素构成）。

• 去掉 7：7 与后面 5,1,3,6,4 构成 5 个逆序 → 减 5 ✗；
• 去掉 5：与 1,3,4 → 3 个 ✓；
• 去掉 3：与前面 7,5,9 → 2 个？9 在 3 前但 9>3 ✓ 也算：7>3 ✓、5>3 ✓、1<3 ✗、9>3 ✓ → 3 个 ✓；
• 去掉 6：7>6 ✓、9>6 ✓ → 2 个 ✗？前面 7、9，后面 4：7>6 ✓(前)、9>6 ✓(前)、4<6 (后) 0 → 共 2 ✗。

答案：B、C（各减 3）。

易错提醒

① 删元素减少的逆序对 = 该元素与两侧构成的逆序对总数；② 逐元素数「前面比它大 + 后面比它小」。