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

题解：学而思编程逆序对

news 2026/6/11 19:23:34

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

学而思编程：逆序对

【题目描述】

对于一个包含N NN个非负整数的数组A [ 1.. n ] A[1..n]A[1..n]，如果有i < j i<ji<j，且A [ i ] > A [ j ] A[i]>A[j]A[i]>A[j]，则称( A [ i ] , A [ j ] ) (A[i],A[j])(A[i],A[j])为数组A AA中的一个逆序对。

例如，数组( 3 ， 1 ， 4 ， 5 ， 2 ) (3，1，4，5，2)(3，1，4，5，2)的逆序对有( 3 , 1 ) , ( 3 , 2 ) , ( 4 , 2 ) , ( 5 , 2 ) (3,1),(3,2),(4,2),(5,2)(3,1),(3,2),(4,2),(5,2)，共4 44个。

给定一个数组，求该数组中包含多少个逆序对。

【输入】

第一行，一个数n nn，表示数组中有n nn个数。

第二行n nn个数，表示给定的数组。数组中每个数字不超过10 9 10^9109。

【输出】

输出数组中逆序对的数目。

【输入样例】

6 5 4 2 6 3 1

【输出样例】

【算法标签】

#归并排序

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=500005;intn;// 数组长度inta[N],b[N];// a: 原始数组, b: 临时数组intans;// 逆序对数量// 归并排序函数，计算逆序对数量voidmerge_sort(intl,intr){if(l==r)return;// 如果子数组只有一个元素，则不需要排序，直接返回intmid=(l+r)/2;// 计算中点merge_sort(l,mid);// 递归地对左半部分进行归并排序merge_sort(mid+1,r);// 递归地对右半部分进行归并排序intx=l,y=mid+1;// x: 左半部分的指针, y: 右半部分的指针intcnt=l-1;// b数组的指针// 合并两个有序子数组while(x<=mid&&y<=r)// 只要左右两端子数组都不为空{if(a[x]<=a[y])// 将两段子数组左端点较小者插入b数组{b[++cnt]=a[x];// 左半部分元素较小x++;}else// 右半部分元素较小{b[++cnt]=a[y];// 右半部分元素较小y++;ans+=mid-x+1;// 统计逆序对数量}}// 合并过程中其中一个子数组的元素已全部合并完成，而另一个子数组仍有剩余元素的情况for(inti=x;i<=mid;i++)// 如果左半部分还有剩余的元素，将它们复制到b中{b[++cnt]=a[i];}for(inti=y;i<=r;i++)// 如果右半部分还有剩余的元素，将它们复制到b中{b[++cnt]=a[i];}for(inti=l;i<=r;i++)// 将b中已经排序好的部分复制回a中，完成合并{a[i]=b[i];}}signedmain(){cin>>n;// 读取数组长度for(inti=1;i<=n;i++)// 读取数组元素{cin>>a[i];}merge_sort(1,n);// 调用归并排序函数cout<<ans<<endl;// 输出逆序对数量return0;}