逆序对——归并排序

逆序对满足a[i]a[j]且ij这两个条件25级校队训练赛502 - Virtual Judgehttps://vjudge.net/contest/808881#problem/D题目描述现有n个数组成了一个序列求这段正整数序列中逆序对的数目并输出解题思路采用归并排序的方法进行计算代码展现第一种#include bits/stdc.husing namespace std;int n,a[500010],c[500010];long long ans;void msort(int b,int e)//b为左边界e为右边界{if(be)return;//当左右边界相等的时候递归结束int mid(be)/2,ib,jmid1,kb;//mid将数据分成了左半部分和右半部分//i和j此时为左右两部分开始的值k是临时数组c的索引下标//k专门标记要把元素写到临时数组c的那一个位置 用于合并两个有序子数组msort(b,mid),msort(mid1,e);//保证左右区间都是严格升序的有序数组while(imidje)//i不能超过左半部分的最右边j不能超过右边界{if(a[i]a[j])c[k]a[i];//左元素小于右元素//把a[i]写到临时数组的k位置else{c[k]a[j];//左元素大于右元素此时满足a[i]a[j]ij这个条件//把a[j]写到临时数组的k位置ansmid-i1;//逆序对数量左区间剩余未遍历的元素个数mid-i1}}while(imid)c[k]a[i];//合并循环结束后把元素写入c数组中不产生多余的逆序对while(je)c[k]a[j];//合并循环结束后把元素写入c数组中不产生多余的逆序对for(int lb;le;l)a[l]c[l];//把存入临时数组c中的数据拷贝回a数组中更新值}int main(){cinn;for(int i1;in;i)cina[i];msort(1,n);coutans;return 0;}第二种#include bits/stdc.husing namespace std;const int N 500010;int a[N], tmp[N];long long ans 0;void merge(int l, int r){if(l r) return;int mid (l r) /2;merge(l, mid);merge(mid 1, r);int i l, j mid 1, k l;while(i mid j r){if(a[i] a[j]){tmp[k] a[i]; }else{ tmp[k] a[j];ans mid - i 1; }}while(i mid)tmp[k] a[i];while(j r)tmp[k] a[j];for(int p l; p r; p)a[p] tmp[p];}int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin n;for(int i 1; i n; i){cin a[i];}merge(1, n);cout ans endl;return 0;}两种代码中的核心算法始终为void msort(int b,int e)//b为左边界e为右边界{if(be)return;//当左右边界相等的时候递归结束int mid(be)/2,ib,jmid1,kb;//mid将数据分成了左半部分和右半部分//i和j此时为左右两部分开始的值k是临时数组c的索引下标//k专门标记要把元素写到临时数组c的那一个位置 用于合并两个有序子数组msort(b,mid),msort(mid1,e);//保证左右区间都是严格升序的有序数组while(imidje)//i不能超过左半部分的最右边j不能超过右边界{if(a[i]a[j])c[k]a[i];//左元素小于右元素//把a[i]写到临时数组的k位置else{c[k]a[j];//左元素大于右元素此时满足a[i]a[j]ij这个条件//把a[j]写到临时数组的k位置ansmid-i1;//逆序对数量左区间剩余未遍历的元素个数mid-i1}}while(imid)c[k]a[i];//合并循环结束后把元素写入c数组中不产生多余的逆序对while(je)c[k]a[j];//合并循环结束后把元素写入c数组中不产生多余的逆序对for(int lb;le;l)a[l]c[l];//把存入临时数组c中的数据拷贝回a数组中更新值}