CSP-S 2026 第一轮 第 14 题：若把判断条件中的 a[i] <= a[j] 改成 a[i] < a[j]

题目

用归并排序统计逆序对，合并部分的核心代码为：

若把判断条件中的 a[i] <= a[j] 改成 a[i] < a[j]，则 ans 统计出的结果（ ）。

// 分并 a[l..mid] 与 a[mid+1..r]，同时累加逆序对
if (a[i] <= a[j]) {
    tmp[k++] = a[i++]; // 取左半段元素
} else {
    tmp[k++] = a[j++]; // 取右半段元素
    ans += mid - i + 1;
}

选项

• A. 完全不变
• B. 变为原来的两倍
• C. 变为满足 $i < j$ 且 $a[i] \ge a[j]$ 的数对个数
• D. 变为原来的一半

答案

C

题解

选 C。

归并时，左右两段都已经有序：

• 原条件为 a[i] <= a[j]：只有当 a[i] > a[j] 时才进入 else，统计的是严格逆序对。
• 改成 a[i] < a[j]：当 a[i] >= a[j] 时就会进入 else，因此相等的元素也会被统计。

进入 else 时，左半段剩余的元素都满足 \[ a[i],a[i+1],\ldots,a[mid]\ge a[j], \] 所以 ans += mid - i + 1 正好统计这些数对。左半段元素的原始下标都小于右半段元素的原始下标，因此最终统计的是 原数组中满足 \(i<j\) 且 \(a[i]\ge a[j]\) 的数对个数。

例如数组 [2, 2]，原来统计结果为 0，修改后为 1。