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

目描述给定一个长度为 n 的整数数列请你计算数列中的逆序对的数量。逆序对的定义如下对于数列的第 i 个和第 j 个元素如果满足 ij 且 a[i]a[j]则其为一个逆序对否则不是。输入格式第一行包含整数 nn表示数列的长度。第二行包含 nn 个整数表示整个数列。输出格式输出一个整数表示逆序对的个数。数据范围1≤n≤100000数列中的元素的取值范围 [1,109]。输入样例6 2 3 4 5 6 1输出样例5思路解析算法归并排序 Quick Sort 时间复杂度O(nlog(n))解题思路归并排序是一种分治算法。它将一个大的数组不断分成两个子数组递归地对两个子数组进行排序然后再将排好序的子数组合并起来。代码// 包含C标准输入输出流头文件用于cout输出 #include iostream // 使用标准命名空间避免每次调用标准库都写std:: using namespace std; // 给long long长整型起别名LL // 逆序对数量可能极大int会溢出必须用long long存储 typedef long long LL; // 定义数组最大长度1e510100010满足题目数据范围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] 右半区间 [mid1, r] // res 累加左区间内部逆序对 右区间内部逆序对 LL res merge_sort(q, l, mid) merge_sort(q, mid 1, r); // 双指针初始化 // i指向左区间的起始位置 l // j指向右区间的起始位置 mid1 // 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; }一、主题与核心目标讲解经典算法题「逆序对的数量」摒弃低效的暴力解法重点传授基于归并排序的分治求解方法让学习者掌握高效算法思路并深入理解分治思想的实际应用。二、逆序对定义与题目规则逆序对概念给定序列中下标满足ij且对应元素a[i]a[j]的数对即为逆序对举例说明序列[3,1,2]包含(3,1)、(3,2)两个逆序对答案为 2输入输出输入序列长度 n 和整数序列输出逆序对总数数据限制n 最大为 10⁵对算法效率有硬性要求。三、暴力解法分析淘汰方案实现思路双重循环遍历所有数对逐一判断并统计逆序对致命缺陷时间复杂度为O(n²)当 n10⁵时运算量达 10¹⁰次远超计算机每秒 10⁸次的运算极限必然超时无法通过测试。四、核心解题思想分治 归并排序分治核心逻辑将整个序列的逆序对拆分为三部分求和左半区间内部逆序对 右半区间内部逆序对 左右区间跨元素逆序对归并排序适配性递归将序列拆分至单个元素单元素无逆序对自下而上合并有序子区间利用区间有序性高效统计跨区间逆序对这是算法的核心关键。五、算法完整步骤视频将算法拆解为递归拆分、合并统计、返回结果三步逻辑清晰递归拆分定义merge_sort递归函数以区间[l,r]为处理范围终止条件lr返回 0计算中点mid拆分区间递归求解左右子区间的逆序对数量合并统计双指针遍历左右有序子区间比较元素大小左元素≤右元素不构成逆序对直接合并左元素 右元素左区间剩余所有元素均大于右元素一次性统计mid-i1个逆序对用临时数组存储合并结果最终复制回原数组保证上层递归的区间有序性返回结果递归函数最终返回总逆序对数量。六、代码实现与关键细节提供 C 完整可运行代码并强调 4 个核心细节避免程序出错数据类型必须用long long存储结果防止数值溢出10⁵长度的序列逆序对数量超 int 范围效率优化用位运算l r 1计算中点效率高于普通除法临时数组合并时必须用临时数组防止覆盖原数组未比较元素数据回写合并完成后将有序序列复制回原数组保证递归正确性。七、算法效率分析时间复杂度为O(nlogn)递归拆分层数为logn每一层合并需遍历全数组O (n)该复杂度完美适配 n10⁵的数据范围。八、高频问题答疑针对学习者最易困惑的 3 个问题逐一解答递归后区间始终有序归并排序从单元素天然有序开始合并合并后的区间保持有序统计公式mid-i1的原理左区间有序a[i]a[j]时i 到 mid 的所有元素都能与 a [j] 构成逆序对不推荐快速排序快排无法利用有序性高效统计跨区间逆序对实现复杂且效率不稳定。九、总结本题的核心是借助归并排序的分治思想和区间有序性将暴力解法的 O (n²) 复杂度优化为 O (nlogn)通过「拆分问题 - 递归求解 - 合并统计」的流程高效解决逆序对统计问题同时夯实分治思想的应用基础。✅ 归并排序求逆序对的本质把数组拆成两个子区间递归算出两个区间内部的逆序对利用「两个区间已经有序」的特点在合并时快速算出所有跨区间逆序对