当前位置：首页 > news >正文

Acwing基础课第788题-简单-逆序对的数量

news 2026/7/2 9:00:52

目描述

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 nn，表示数列的长度。

第二行包含 nn 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1≤n≤100000

数列中的元素的取值范围 [1,109]。

输入样例

6 2 3 4 5 6 1

输出样例

思路解析：

算法：归并排序（ Quick Sort ）

时间复杂度：O(nlog(n))

解题思路：

归并排序是一种分治算法。它将一个大的数组不断分成两个子数组，递归地对两个子数组进行排序，然后再将排好序的子数组合并起来。

代码：

// 包含C++标准输入输出流头文件，用于cout输出 #include <iostream> // 使用标准命名空间，避免每次调用标准库都写std:: using namespace std; // 给long long长整型起别名LL // 逆序对数量可能极大，int会溢出，必须用long long存储 typedef long long LL; // 定义数组最大长度：1e5+10（100010），满足题目数据范围，+10防止数组越界 const int N = 1e5 + 10; // a[]：存储原始输入的数组 // tmp[]：归并排序的**临时辅助数组**，用于暂存合并后的有序元素 int a[N], tmp[N]; /** * @brief 归并排序函数，同时统计区间[l, r]内的逆序对数量 * @param q 待排序/统计的数组 * @param l 区间左边界 * @param r 区间右边界 * @return LL 当前区间内的逆序对总数 */ LL merge_sort(int q[], int l, int r) { // 递归终止条件：区间只有一个数 或 无数据，没有逆序对，返回0 if (l >= r) return 0; // 计算区间中点：等价于 (l + r) / 2，位运算>>1效率更高 int mid = l + r >> 1; // 递归处理左半区间 [l, mid] + 右半区间 [mid+1, r] // res 累加：左区间内部逆序对 + 右区间内部逆序对 LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r); // 双指针初始化： // i：指向左区间的起始位置 l // j：指向右区间的起始位置 mid+1 // k：指向临时数组tmp的起始位置 0 int k = 0, i = l, j = mid + 1; // 核心：合并两个有序区间，同时统计**跨区间的逆序对** while (i <= mid && j <= r) { // 左区间当前数 ≤ 右区间当前数：无逆序对，直接放入临时数组 if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; // 左区间当前数 > 右区间当前数：**找到逆序对** else { // 关键！左区间中从i到mid的所有数，都比q[j]大 // 逆序对数量 += mid - i + 1 res += mid - i + 1; // 将右区间当前数放入临时数组 tmp[k ++ ] = q[j ++ ]; } } // 左区间还有剩余元素（全部有序），直接复制到临时数组 while (i <= mid) tmp[k ++ ] = q[i ++ ]; // 右区间还有剩余元素（全部有序），直接复制到临时数组 while (j <= r) tmp[k ++ ] = q[j ++ ]; // 把临时数组tmp中排好序的元素，复制回原数组q的[l, r]区间 for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; // 返回当前区间的总逆序对数量（内部+跨区间） return res; } int main() { // n：数组元素个数 int n; // 输入n scanf("%d", &n); // 循环输入n个元素，存入数组a for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); // 调用归并排序，输出整个数组的逆序对总数 cout << merge_sort(a, 0, n - 1) << endl; // 程序正常结束 return 0; }

一、主题与核心目标

讲解经典算法题「逆序对的数量」，摒弃低效的暴力解法，重点传授基于归并排序的分治求解方法，让学习者掌握高效算法思路，并深入理解分治思想的实际应用。

二、逆序对定义与题目规则

逆序对概念：给定序列中，下标满足i<j且对应元素a[i]>a[j]的数对，即为逆序对；
举例说明：序列[3,1,2]包含(3,1)、(3,2)两个逆序对，答案为 2；
输入输出：输入序列长度 n 和整数序列，输出逆序对总数；
数据限制：n 最大为 10⁵，对算法效率有硬性要求。

三、暴力解法分析（淘汰方案）

实现思路：双重循环遍历所有数对，逐一判断并统计逆序对；
致命缺陷：时间复杂度为O(n²)，当 n=10⁵时，运算量达 10¹⁰次，远超计算机每秒 10⁸次的运算极限，必然超时，无法通过测试。

四、核心解题思想：分治 + 归并排序

分治核心逻辑：将整个序列的逆序对拆分为三部分求和：左半区间内部逆序对 + 右半区间内部逆序对 + 左右区间跨元素逆序对；
归并排序适配性：递归将序列拆分至单个元素（单元素无逆序对），自下而上合并有序子区间，利用区间有序性高效统计跨区间逆序对，这是算法的核心关键。

五、算法完整步骤

视频将算法拆解为递归拆分、合并统计、返回结果三步，逻辑清晰：

递归拆分：定义merge_sort递归函数，以区间[l,r]为处理范围；终止条件l>=r（返回 0）；计算中点mid拆分区间，递归求解左右子区间的逆序对数量；
合并统计：双指针遍历左右有序子区间，比较元素大小：
- 左元素≤右元素：不构成逆序对，直接合并；
- 左元素 > 右元素：左区间剩余所有元素均大于右元素，一次性统计mid-i+1个逆序对；
- 用临时数组存储合并结果，最终复制回原数组，保证上层递归的区间有序性；
返回结果：递归函数最终返回总逆序对数量。